Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure the resistance of a Boolean function to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. The binary LCD codes presented in this paper have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems.

Secret sharing is a very useful way to maintain secrecy of private data when stored in a distributed way among several nodes. Two significant questions in this area are 1. how to accommodate new nodes and assign shares to the new nodes, the problem becomes harder if the number of joining nodes or the access structure is not known in advance and can be (potentially) unbounded and 2. to reduce the computational complexity of secret sharing schemes. In this paper we propose two new constructions of such secret sharing schemes based on different combinatorial structures. The first construction is based on generalized paths joining the opposite vertices of a hypercube which has been divided into smaller hypercubes. The second construction is a forest- based construction utilizing a dynamic data structure technique known as fractional cascading. The generalized path we call a pavement is new to this paper. Both our constructions use a new secret redistribution scheme to assign and re-assign shares to nodes. Towards the second question we show that allowing certain trade-offs, the constructions are implementable by $AC^0$ circuits which is the lowest complexity class in which secret sharing and reconstruction is possible. To the best of the knowledge of the authors, none of the similar existing schemes (evolving or dynamic) are $AC^0$ computable and this paper for the first time combines the idea of hypercubes and dynamic data structures with secret sharing for preserving long-term confidentiality of secret data.

The common approach in secure communication channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, protocols like QUIC or DTLS which run over a non-reliable transport such as UDP, do not---and in fact cannot---close the connection if packets are lost or arrive in a different order. Those protocols instead have to carefully catch effects arising naturally in unreliable networks, usually by using a sliding-window technique where ciphertexts can be decrypted correctly as long as they are not misplaced too far. In order to be able to capture QUIC and the newest DTLS version 1.3, we introduce a generalized notion of robustness of cryptographic channels. This property can capture unreliable network behavior and guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We show that robustness is orthogonal to the common notion of integrity for channels, but together with integrity and chosen-plaintext security it provides a robust analogue of chosen-ciphertext security of channels. In contrast to prior work, robustness allows us to study packet encryption in the record layer protocols of QUIC and of DTLS 1.3 and the novel sliding-window techniques both protocols employ. We show that both protocols achieve robust chosen-ciphertext security based on certain properties of their sliding-window techniques and the underlying AEAD schemes. Notably, the robustness needed in handling unreliable network messages requires both record layer protocols to tolerate repeated adversarial forgery attempts. This means we can only establish non-tight security bounds (in terms of AEAD integrity), a security degration that was missed in earlier protocol drafts. Our bounds led the responsible IETF working groups to introduce concrete forgery limits for both protocols and the IRTF CFRG to consider AEAD usage limits more broadly.

As the fault based analysis techniques are becoming more and more powerful, there is a need to streamline the existing tools for better accuracy and ease of use. In this regard, we propose a machine learning assisted tool that can be used in the context of a differential fault analysis. In particular, finding the exact fault location by analyzing the XORed output of a stream cipher/ stream cipher based design is somewhat non-trivial. Traditionally, Pearson's correlation coefficient is used for this purpose. We show that a machine learning method is more powerful than the existing correlation coefficient, aside from being simpler to implement. As a proof of concept, we take two variants of Grain-128a (namely a stream cipher, and a stream cipher with authentication), and demonstrate that machine learning can outperform correlation with the same training/testing data. Our analysis shows that the machine learning can be considered as a replacement for the correlation in the future research works.

Physically unclonable function (PUF) is a technology to generate a device-unique identifier using process variation. PUF enables a cryptographic key that appears only when the chip is active, providing an efficient countermeasure against reverse-engineering attacks. In this paper, we explore the data conversion that digitizes a physical quantity representing PUF’s uniqueness into a numerical value as a new attack surface. We focus on time-to-digital converter (TDC) that converts time duration into a numerical value. We show the first signal injection attack on a TDC by manipulating its clock, and verify it through experiments on an off-the-shelf TDC chip. Then, we show how to leverage the attack to reveal a secret key protected by a PUF that uses a TDC for digitization.

In this short trivial note we argue that, assuming Generalized Continuum Hypothesis to be true, it is impractical to use encryption with $Key \in \{ 0, 1 \}^K$ and $Message \in \{ 0, 1 \}^M$ such that $\aleph_0 \leqslant \mathrm{card}\,K < \mathrm{card}\,M$, because "complexity" of the known-plaintext bruteforce attack equals "complexity" of a single $En/Decrypt(Key, Message)$ "computation" then.

We define and study a new cryptographic primitive, named One-One Constrained Pseudorandom Functions. In this model there are two parties, Alice and Bob, that hold a common random string $K$, where Alice in addition holds a predicate $f:[N] \rightarrow \{ 0,1 \}$ and Bob in addition holds an input $x \in [N]$. We then let Alice generate a key $K_f$ based on $f$ and $K$, and let Bob evaluate a value $K_x$ based on $x$ and $K$. We consider a third party that sees the values $(x,f,K_f)$ and the goal is to allow her to reconstruct $K_x$ whenever $f(x)=1$, while keeping $K_x$ pseudorandom whenever $f(x)=0$. This primitive can be viewed as a relaxation of constrained PRFs, such that there is only a single key query and a single evaluation query. We focus on the information-theoretic setting, where the one-one cPRF has perfect correctness and perfect security. Our main results are as follows. 1. A Lower Bound. We show that in the information-theoretic setting, any one-one cPRF for punctured predicates is of exponential complexity (and thus the lower bound meets the upper bound that is given by a trivial construction). This stands in contrast with the well known GGM-based punctured PRF from OWF, which is in particular a one-one cPRF. This also implies a similar lower bound for all NC1. 2. New Constructions. On the positive side, we present efficient information-theoretic constructions of one-one cPRFs for a few other predicate families, such as equality predicates, inner-product predicates, and subset predicates. We also show a generic AND composition lemma that preserves complexity. 3. An Amplification to standard cPRF. We show that all of our one-one cPRF constructions can be amplified to a standard (single-key) cPRF via any key-homomorphic PRF that supports linear computations. More generally, we suggest a new framework that we call the double-key model which allows to construct constrained PRFs via key-homomorphic PRFs. 4. Relation to CDS. We show that one-one constrained PRFs imply conditional disclosure of secrets (CDS) protocols. We believe that this simple model can be used to better understand constrained PRFs and related cryptographic primitives, and that further applications of one-one constrained PRFs and our double-key model will be found in the future, in addition to those we show in this paper.

Proxy re-encryption (PRE), formalized by Blaze et al. in 1998, allows a proxy entity to delegate the decryption right of a ciphertext from one party to another without obtaining the information of the plaintext. In recent years, many studies have explored how to construct PRE schemes that support fine-grained access control for complex application scenarios, such as identity-based PRE and attribute-based PRE. Besides, in order to achieve more flexible access control, the predicate proxy re-encryption (PPRE) is further studied. However, existing PPRE is restricted with the inner product predicate function. Therefore, how to realize the PPRE of arbitrary predicate function is still a problem to be solved. In this manuscript, we propose a secure generic construction of predicate proxy key re-encapsulation mechanism built from a ``linear'' predicate key encapsulation mechanism. Since the secure key encapsulation mechanism can be used as a building block to construct public key encryption, we can obtain a PPRE from our construction. As a result, the results open up new avenues for building more flexible and fine-grained PPRE.

We develop two variants of Cocks' identity-based encryption. One variant has faster encryption, where the most time-consuming part only requires several modular multiplications. The other variant makes the first variant anonymous under suitable complexity assumptions, while its decryption efficiency is about twice lower than the first one. Both the variants have ciphertext expansion twice more extensive than the original Cocks' identity-based encryption. To alleviate the issue of the second variant's large ciphertext expansion, we consider using it to construct a public-key encryption with keyword search scheme with a fast encryption algorithm.

Auditing a secure multiparty computation (MPC) protocol entails the validation of the protocol transcript by a third party that is otherwise untrusted. In this work we introduce the concept of end-to-end verifiable MPC (VMPC), that requires the validation to provide a correctness guarantee even in the setting that all servers, trusted setup primitives and all the client systems utilized by the input-providing users of the MPC protocol are subverted by an adversary. To instantiate VMPC, we introduce a new concept in the setting of zero-knowlegde protocols that we term crowd verifiable zero-knowledge (CVZK). A CVZK protocol enables a prover to convince a set of verifiers about a certain statement, even though each one individually contributes a small amount of entropy for verification and some of them are adversarially controlled. Given CVZK, we present a VMPC protocol that is based on discrete-logarithm related assumptions. At the high level of adversity that VMPC is meant to withstand, it is infeasible to ensure perfect correctness, thus we investigate the classes of functions and verifiability relations that are feasible in our framework, and present a number of possible applications the underlying functions of which can be implemented via VMPC.

We study the rational behaviors of participants in committee-based blockchains. Committee-based blockchains rely on specific blockchain consensus that must be guaranteed in presence of rational participants. We consider a simplified blockchain consensus algorithm based on existing or proposed committee-based blockchains that encapsulates the main actions of the participants: voting for a block, and checking its validity. Knowing that those actions have costs, and achieving the consensus gives rewards to committee members, we study using game theory how strategic players behave while trying to maximizing their gains. We consider different reward schemes, and found that in each setting, there exist equilibria where blockchain consensus is guaranteed; in some settings however, there can be coordination failures hindering consensus. Moreover, we study equilibria with trembling participants, which is a novelty in the context of committee-based blockchains. Trembling participants are rational that can do unintended actions with a low probability. We found that in presence of trembling participants, there exist equilibria where blockchain consensus is guaranteed; however, when only voters are rewarded, there also exist equilibria where validity can be violated.

Token-curated registries (TCRs) are a mechanism by which a set of users are able to jointly curate a reputable list about real-world information. Entries in the registry may have any form, so this primitive has been proposed for use -- and deployed -- in a variety of decentralized applications, ranging from the simple joint creation of lists to helping to prevent the spread of misinformation online. Despite this interest, the security of this primitive is not well understood, and indeed existing constructions do not achieve strong or provable notions of security or privacy. In this paper, we provide a formal cryptographic treatment of TCRs as well as a construction that provably hides the votes cast by individual curators. Along the way, we provide a model and proof of security for an underlying voting scheme, which may be of independent interest.

Recent studies have suggested various side-channel attacks for eavesdropping sound by analyzing the side effects of sound waves on nearby objects (e.g., a bag of chips and window) and devices (e.g., motion sensors). These methods pose a great threat to privacy, however they are limited in one of the following ways: they (1) cannot be applied in real time (e.g., Visual Microphone), (2) are not external, requiring the attacker to compromise a device with malware (e.g., Gyrophone), or (3) are not passive, requiring the attacker to direct a laser beam at an object (e.g., laser microphone). In this paper, we introduce "Lamphone," a novel side-channel attack for eavesdropping sound; this attack is performed by using a remote electro-optical sensor to analyze a hanging light bulb’s frequency response to sound. We show how fluctuations in the air pressure on the surface of the hanging bulb (in response to sound), which cause the bulb to vibrate very slightly (a millidegree vibration), can be exploited by eavesdroppers to recover speech and singing, passively, externally, and in real time. We analyze a hanging bulb’s response to sound via an electro-optical sensor and learn how to isolate the audio signal from the optical signal. Based on our analysis, we develop an algorithm to recover sound from the optical measurements obtained from the vibrations of a light bulb and captured by the electro-optical sensor. We evaluate Lamphone’s performance in a realistic setup and show that Lamphone can be used by eavesdroppers to recover human speech (which can be accurately identified by the Google Cloud Speech API) and singing (which can be accurately identified by Shazam and SoundHound) from a bridge located 25 meters away from the target room containing the hanging light bulb.

We give a lattice reduction algorithm that achieves root Hermite factor $k^{1/(2k)}$ in time $k^{k/8 + o(k)}$ and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time $k^{k/(2e) + o(k)}$. A cost of $k^{k/8 + o(k)}$ was previously mentioned as potentially achievable (Hanrot-Stehlé'10) or as a heuristic lower bound (Nguyen'10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below $k^{k/8 + o(k)}$ for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.

Logic synthesis is a fundamental step in the realization of modern integrated circuits. It has traditionally been employed for the optimization of CMOS-based designs, as well as for emerging technologies and quantum computing. Recently, it found application in minimizing the number of AND gates in cryptography benchmarks represented as xor-and graphs (XAGs). The number of AND gates in an XAG, which is called the logic network’s multiplicative complexity, plays a critical role in various cryptography and security protocols such as fully homomorphic encryption (FHE) and secure multi-party computation (MPC). Further, the number of AND gates is also important to assess the degree of vulnerability of a Boolean function, and influences the cost of techniques to protect against side-channel attacks. However, so far a complete logic synthesis flow for reducing the multiplicative complexity in logic networks did not exist or relied heavily on manual manipulations. In this paper, we present a logic synthesis toolbox for cryptography and security applications. The proposed tool consists of powerful transformations, namely resubstitution, refactoring, and rewriting, specifically designed to minimize the multiplicative complexity of an XAG. Our flow is fully automatic and achieves significant results over both EPFL benchmarks and cryptography circuits. We improve the best-known results for cryptography up to 59%, resulting in a normalized geometric mean of 0.82.

We give a lower bound for the size of the value set of almost perfect nonlinear (APN) functions \(F\colon \mathbb{F}_2^n \to \mathbb{F}_2^n\) in explicit form and proof it with methods of linear programming. It coincides with the bound given in [CHP17]. For \(n\) even it is \(\frac{ 2^n + 2 }{3}\) and sharp as the simple example \(F(x) = x^3\) shows. The sharp lower bound for \(n\) odd has to lie between \(\frac{ 2^n + 1 }{3}\) and \(2^{n-1}\). Sharp bounds for the cases \(n = 3\) and \(n = 5\) are explicitly given.

Secure aggregation is a cryptographic primitive that enables a server to learn the sum of the vector inputs of many clients. Bonawitz et al. (CCS 2017) presented a construction that incurs computation and communication for each client linear in the number of parties. While this functionality enables a broad range of privacy preserving computational tasks, scaling concerns limit its scope of use. We present the first constructions for secure aggregation that achieve polylogarithmic communication and computation per client. Our constructions provide security in the semi-honest and the semi-malicious setting where the adversary controls the server and a $\gamma$-fraction of the clients, and correctness with up to $\delta$-fraction dropouts among the clients. Our constructions show how to replace the complete communication graph of Bonawitz et al., which entails the linear overheads, with a $k$-regular graph of logarithmic degree while maintaining the security guarantees. Beyond improving the known asymptotics for secure aggregation, our constructions also achieve very efficient concrete parameters. The semi-honest secure aggregation can handle a billion clients at the per client cost of the protocol of Bonawitz et al. for a thousand clients. In the semi-malicious setting with $10^4$ clients, each client needs to communicate only with $3\%$ of the clients to have a guarantee that its input has been added together with the inputs of at least $5000$ other clients, while withstanding up to $5\%$ corrupt clients and $5\%$ dropouts. We also show an application of secure aggregation to the task of secure shuffling which enables the first cryptographically secure instantiation of the shuffle model of differential privacy.

Multivariate public key cryptography is a candidate for post-quantum cryptography, and it allows generating particularly short signatures and fast verification. The Rainbow signature scheme proposed by J. Ding and D. Schmidt is such a multivariate cryptosystem and is considered secure against all known attacks. The Rainbow-Band-Separation attack recovers a secret key of Rainbow by solving certain systems of quadratic equations, and its complexity is estimated by the well-known indicator called the degree of regularity. However, the degree of regularity generally is larger than the solving degree in experiments, and an accurate estimation cannot be obtained. In this paper, we propose a new indicator for the complexity of the Rainbow-Band-Separation attack using the $F_4$ algorithm, which gives a more precise estimation compared to one using the degree of regularity. This indicator is deduced by the two-variable power series $$\frac{\prod _{i=1}^m(1-t_1^{d_{i1}}t_2^{d_{i2}})}{(1-t_1)^{n_1}(1-t_2)^{n_2}},$$ which coincides with the one-variable power series at $t_1=t_2$ deriving the degree of regularity. Moreover, we show a relation between the Rainbow-Band-Separation attack using the hybrid approach and the HighRank attack. By considering this relation and our indicator, we obtain a new complexity estimation for the Rainbow-Band-Separation attack. Consequently, we are able to understand the precise security of Rainbow against the Rainbow-Band-Separation attack using the $F_4$ algorithm.

Currently the National Institute of Standards and Technology (NIST) is engaged in a post-quantum standardization effort, analyzing numerous candidate schemes to provide security against the advancing threat of quantum computers. Among the candidates in the second round of the standardization process is Rainbow, a roughly 15 year old digital signature scheme based on multivariate systems of equations. While there are many attack avenues for Rainbow, the parameters have to date seemed balanced in such a way to make every attack sufficiently costly that it meets the security levels specified by NIST in their standardization effort. One type of attack against Rainbow has historically outperformed empirically its theoretical complexity: the Rainbow Band Separation (RBS) attack. We explain this discrepancy by providing a tighter theoretical analysis of the attack complexity. While previous analyses assumed that the system of equations derived in the attack are generic, our analysis uses the fact that they are structured to justify tighter bounds on the complexity. As a result, we can prove under the same set of assumptions used to justify the analysis in the Rainbow submission specification that none of the parameters of Rainbow achieve their claimed security level. Specifically, the level I, III and V parameter sets fall short of their claimed security levels by at least 3, 6 and 10 bits, respectively. We then apply our analysis to suggest the small parameter changes necessary to guarantee that Rainbow can meet the NIST security levels.

Classical definitions for secure multiparty computation assume the existence of a single adversarial entity controlling the set of corrupted parties. Intuitively, the definition requires that the view of the adversary, corrupting $t$ parties, in a real-world execution can be simulated by an adversary in an ideal model, where parties interact only via a trusted-party. No restrictions, however, are imposed on the view of honest parties in the protocol, thus, if honest parties obtain information about the private inputs of other honest parties -- it is not counted as a violation of privacy. This is arguably undesirable in many situations that fall into the MPC framework. Nevertheless, there are secure protocols (e.g., the 2-round multiparty protocol of Ishai et al.~[CRYPTO 2010] tolerating a single corrupted party) that instruct the honest parties to reveal their private inputs to all other honest parties (once the malicious party is somehow identified). In this paper, we put forth a new security notion, which we call \textit{FaF-security}, extending the classical notion. In essence, $(t,h^*)$-FaF-security requires the view of a subset of up to $h^*$ honest parties to also be simulatable in the ideal model (in addition to the view of the malicious adversary, corrupting up to $t$ parties). This property should still hold, even if the adversary leaks information to honest parties by sending them non-prescribed messages. We provide a thorough exploration of the new notion, investigating it in relation to a variety of existing security notions. We further investigate the feasibility of achieving FaF-security and show that every functionality can be computed with (computational) $(t,h^*)$-FaF full-security, if and only if $2t+ h^*<m$. Interestingly, the lower-bound result actually shows that even fair FaF-security is impossible in general when $2t+ h^*\ge m$ (surprisingly, the view of the malicious attacker is not used as the trigger for the attack). We also investigate the optimal round complexity for $(t,h^*)$-FaF-secure protocols and give evidence that the leakage of private inputs of honest parties in the protocol of Ishai et al.~[CRYPTO 2010] is inherent. Finally, we investigate the feasibility of statistical/perfect FaF-security, employing the viewpoint used by Fitzi et al.~[ASIACRYPT 1999] for \textit{mixed-adversaries}.

Personal data exchange and disclosure prevention are widespread problems in our digital world. There are a couple of information technologies embedded in the commercial and government processes. People need to exchange their personal information while using these technologies. And therefore, It is essential to make this exchange is secure. Despite many legal regulations, there are many cases of personal data breaches that lead to undesirable consequences. Reasons for personal data leakage may be adversary attack or data administration error. At the same time, creating complex service interaction and multilayer information security may lead to many inconveniences for the user. Personal data exchange protocol has the following tasks: participant’s data transfer, ensuring information security, providing participants with trust in each other and ensuring service availability. In this paper, we represent a personal data exchange protocol called X. The main idea is to provide personal data encryption on the user side and thus to prevent personal data disclosure and publication. This approach allows us to transfer personal data from user to service only in the form of an encrypted data packet - blob. Each blob can be validated and certified by a personal data inspector who had approved user’s information. It can be any government department or a commercial organization, for example, passport issuing authority, banks, etc. It implies that we can provide several key features for personal data exchange. A requesting service cannot publish the user personal data. It still can perform a validation protocol with an inspector to validate user data. We do not depend on service data administration infrastructure and do not complicate the inspector’s processes by adding additional information about the personal data request. The personal data package has a link between the personal data owner and a service request. Each blob is generated for a single request and has a time limit for a provided encrypted personal data. After this limit, the service can not use a received package. The user cannot provide invalid personal data or use the personal data of another person. We don’t restrict specified cryptographic algorithms usage The X protocol can be implemented with any encryption, digital signature, key generation algorithms which are secure in our adversary model. For protocol description, Russian standardized cryptographic protocols are used. The paper also contains several useful examples of how the X protocol can be implemented in real information systems.

Cryptographic primitives have been designed to be secure against mathematical attacks in a black-box model. Such primitives can be implemented in a way that they are also secure against physical attacks, in a grey-box model. One of the most popular techniques for this purpose is masking. The increased security always comes with a high price tag in terms of implementation cost. In this work, we look at how the traditional design principles of symmetric primitives can be at odds with the optimization of the implementations and how they can evolve to be more suitable for embedded systems. In particular, we take a comparative look at the round 2 candidates of the NIST lightweight competition and their implementation properties in the world of masking.

GIFT-COFB is one of the round 2 candidate algorithms of NIST lightweight cryptography. In this paper we present a forgery attack on GIFT-COFB. In our attack, the block cipher GIFT is viewed as a block box, and for an arbitrary ciphertext $(C, T)$ with at least twice the block length of GIFT-COFB, if an attacker knows arbitrary two successive blocks of message $M$ corresponding to $C$, he/she can forge infinite new valid ciphertexts $(C', T')$ such that for each $(C', T')$, there exists a plaintext $M'$ satisfying $(C', T')$=GIFT-COFB($M'$). The above result shows that GIFT-COFB can not resist against the forgery attack.

We report on two new records: the factorization of RSA-240, a 795-bit number, and a discrete logarithm computation over a 795-bit prime field. Previous records were the factorization of RSA-768 in 2009 and a 768-bit discrete logarithm computation in 2016. Our two computations at the 795-bit level were done using the same hardware and software, and show that computing a discrete logarithm is not much harder than a factorization of the same size. Moreover, thanks to algorithmic variants and well-chosen parameters, our computations were significantly less expensive than anticipated based on previous records. The last page of this paper also reports on the factorization of RSA-250.

The Chinese remainder theorem (CRT)-based multiplier is a new type of hybrid bit-parallel multiplier, which can achieve nearly the same time complexity compared with the fastest multiplier known to date with reduced space complexity. However, the current CRT-based multipliers are only applicable to trinomials. In this paper, we propose an efficient CRT-based bit-parallel multiplier for a special type of pentanomial $x^m+x^{m-k}+x^{m-2k}+x^{m-3k}+1, 5k<m\leq 7k$. Through transforming the non-constant part $x^m+x^{m-k}+x^{m-2k}+x^{m-3k}$ into a binomial, we can obtain relatively simpler quotient and remainder computations, which lead to faster implementation with reduced space complexity compared with classic quadratic multipliers. Moreover, for some $m$, our proposal can achieve the same time delay as the fastest multipliers for irreducible Type II and Type C.1 pentanomials of the same degree, but the space complexities are reduced.

A software watermarking scheme can embed a message into a program without significantly changing its functionality. Moreover, any attempt to remove the embedded message in a marked program will substantially change the functionality of the program. Prior constructions of watermarking schemes focus on watermarking cryptographic functions, such as pseudorandom function (PRF), public key encryption, etc. A natural security requirement for watermarking schemes is collusion resistance, where the adversary’s goal is to remove the embedded messages given multiple marked versions of the same program. Currently, this strong security guarantee has been achieved by watermarking schemes for public key cryptographic primitives from standard assumptions (Goyal et al., CRYPTO 2019) and by watermarking schemes for PRFs from indistinguishability obfuscation (Yang et al., ASIACRYPT 2019). However, no collusion resistant watermarking scheme for PRF from standard assumption is known. In this work, we solve this problem by presenting a generic construction that upgrades a watermarkable PRF without collusion resistance to a collusion resistant one. One appealing feature of our construction is that it can preserve the security properties of the original scheme. For example, if the original scheme has security with extraction queries, the new scheme is also secure with extraction queries. Besides, the new scheme can achieve unforgeability even if the original scheme does not provide this security property. Instantiating our construction with existing watermarking schemes for PRF, we obtain collusion resistant watermarkable PRFs from standard assumptions, offering various security properties.

In this work, we exhibit a hierarchy of polynomial time algorithms solving approximate variants of the Closest Vector Problem (CVP). Our first contribution is a heuristic algorithm achieving the same distance tradeoff as HSVP algorithms, namely $\approx \beta^{\frac{n}{2\beta}}\textrm{covol}(\Lambda)^{\frac{1}{n}}$ for a random lattice $\Lambda$ of rank $n$. Compared to the so-called Kannan's embedding technique, our algorithm allows using precomputations and can be used for efficient batch CVP~instances. This implies that some attacks on lattice-based signatures lead to very cheap forgeries, after a precomputation. Our second contribution is a \emph{proven} reduction from approximating the closest vector with a factor $\approx n^{\frac32}\beta^{\frac{3n}{2\beta}}$ to the Shortest Vector Problem (SVP) in dimension $\beta$.

In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of $ST^2 = \tilde\Omega(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time $\tilde O(\sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains $ST^2 = \tilde\Omega(N)$. In this work, we prove that even with quantum advice, $ST + T^2 = \tilde\Omega(N)$ is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for $S = \tilde O(\sqrt{N})$, ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results. * Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi et al (2015). * Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields a first quantum time-space lower bound for salted collision-finding, which in turn implies that ${PWPP}^{O} \not\subseteq {FBQP}^{O}{/qpoly}$ relative to a random oracle $O$.

Masking is one of the most popular countermeasures to protect cryptographic implementations against side-channel analysis since it is provably secure and can be deployed at the algorithm level. To strengthen the original Boolean masking scheme, several works have suggested using schemes with high algebraic complexity. The Inner Product Masking (IPM) is one of those. In this paper, we propose a unified framework to quantitatively assess the side-channel security of the IPM in a coding-theoretic approach. Specifically, starting from the expression of IPM in a coded form, we use two defining parameters of the code to characterize its side-channel resistance. In order to validate the framework, we then connect it to two leakage metrics (namely signal-to-noise ratio and mutual information, from an information-theoretic aspect) and one typical attack metric (success rate, from a practical aspect) to build a firm foundation for our framework. As an application, our results provide ultimate explanations on the observations made by Balasch et al. at EUROCRYPT'15 and at ASIACRYPT'17, Wang et al. at CARDIS'16 and Poussier et al. at CARDIS'17 regarding the parameter effects in IPM, like higher security order in bounded moment model. Furthermore, we show how to systematically choose optimal codes (in the sense of a concrete security level) to optimize IPM by using this framework. Eventually, we present a simple but effective algorithm for choosing optimal codes for IPM, which is of special interest for designers when selecting optimal parameters for IPM.

In this paper we present a series of applications steming from a formal treatment of linear secret-sharing isomorphisms, which are linear transformations between different secret-sharing schemes defined over vector spaces over a field $\mathbb{F}$ and allow for efficient multiparty conversion from one secret-sharing scheme to the other. This concept generalizes the folklore idea that moving from a secret-sharing scheme over $\mathbb{F}_{p}$ to a secret sharing ``in the exponent'' can be done non-interactively by multiplying the share unto a generator of e.g., an elliptic curve group. We generalize this idea and show that it can also be used to compute arbitrary bilinear maps and in particular pairings over elliptic curves. We include the following practical applications originating from our framework: First we show how to securely realize the Pointcheval-Sanders signature scheme (CT-RSA 2016) in MPC. Second we present a construction for dynamic proactive secret-sharing which outperforms the current state of the art from CCS 2019. Third we present a construction for MPC input certification using digital signatures that we show experimentally to outperform the previous best solution in this area.

Secret sharing-based distributed storage systems are one approach to provide long-term protection of data even against quantum computing. Confidentiality is provided because the shares of data are renewed periodically while integrity is provided by commitment schemes. However, this solution is prohibitively costly and impractical: share renewal requires an information-theoretically secure channel between any two nodes and long-term confidential commitment schemes are computationally impractical for large files. In this paper, we present SAFE, a secret sharing-based long-term secure distributed storage system that leverages a Trusted Execution Environment (TEE) to overcome the above limitations. Share generation and renewal are performed inside the TEE and the shares are securely distributed to the storage servers. We prototype SAFE protocols using a TEE instantiation, and show their efficiency, even for large files, compared to existing schemes.

Skinny is a lightweight tweakable block cipher which received a great deal of cryptanalytic attention following its elegant structure and efficiency. Inspired by the Skinny competitions, multiple attacks on it were reported in different settings (e.g. single vs. related-tweakey) using different techniques (impossible differentials, meet-in-the-middle, etc.). In this paper we revisit some of these attacks, identify issues with several of them, and offer a series of improved attacks which were experimentally verified. Our best attack can attack up to 18 rounds using $2^{60}$ chosen ciphertexts data, $2^{116}$ time, and $2^{112}$ memory.

This paper introduces a logarithmic-size membership proof, Lin2Selector, obtained by iterating a new OR-reduction step, formalized as a standalone argument Lin2Xor. Our main technical contribution is the Lin2-Xor lemma, which establishes the required special soundness for this reduction and thereby enables a clean proof that Lin2Selector is a zero-knowledge argument of knowledge. As an application, we instantiate two setup-free linkable ring signatures via the Fiat–Shamir transform in the ROM: minimalistic L2S-LRS, of length 2(log n)+4 group/scalar elements, and multisignature-friendly L2S-LRS-MS, of length 2(log n)+5, supporting an LSAG-style key image. Both schemes rely only on the standard DLR/DDH assumptions in a black-box prime-order group and allow efficient verification dominated by a single multi-exponentiation, enabling standard batching optimizations. The OR-reduction step Lin2Xor suggests a natural generalization to higher arity. This may enable even more compact one-out-of-many proofs/signatures with lengths approaching (log n)+O(log log n), as well as compact k-out-of-many variants; we leave these as open directions.

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an $s$-bit advice on a randomly chosen function $f\colon [n] \mapsto [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$, i.e., to find $x\in f^{-1}(y)$. Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman [IEEE transactions on Information Theory '80] presented an adaptive inverter that inverts with high probability a random $f$. Fiat and Naor [SICOMP '00] proved that for any $s,q$ with $s^3 q = n^3$ (ignoring low-order terms), an $s$-advice, $q$-query variant of Hellman's algorithm inverts a constant fraction of the image points of any function. Yao [STOC '90] proved a lower bound of $sq\ge n$ for this problem. Closing the gap between the above lower and upper bounds is a long-standing open question. Very little is known for the non-adaptive variant of the question - the inverter chooses its queries in advance. The only known upper bounds, i.e., inverters, are the trivial ones (with $s+q= n$), and the only lower bound is the above bound of Yao. In a recent work, Corrigan-Gibbs and Kogan [TCC '19] partially justified the difficulty of finding lower bounds on non-adaptive inverters, showing that a lower bound on the time/memory tradeoff of non-adaptive inverters implies a lower bound on low-depth Boolean circuits. Bounds that, for a strong enough choice of parameters, are notoriously hard to prove. We make progress on the above intriguing question, both for the adaptive and the non-adaptive case, proving the following lower bounds on restricted families of inverters: - Linear-advice (adaptive inverter): If the advice string is a linear function of $f$ (e.g., $A\times f$, for some matrix $A$, viewing $f$ as a vector in $[n]^n$), then $s+q \in \Omega(n)$. The bound generalizes to the case where the advice string of $f_1 + f_2$, i.e., the coordinate-wise addition of the truth tables of $f_1$ and $f_2$, can be computed from the description of $f_1$ and $f_2$ by a low communication protocol. - Affine non-adaptive decoders: If the non-adaptive inverter has an affine decoder - it outputs a linear function, determined by the advice string and the element to invert, of the query answers - then $s \in \Omega(n)$ (regardless of $q$). - Affine non-adaptive decision trees: If the non-adaptive inversion algorithm is a $d$-depth affine decision tree - it outputs the evaluation of a decision tree whose nodes compute a linear function of the answers to the queries - and $q < cn$ for some universal $c>0$, then $s\in \Omega(n/d \log n)$.

The Internet of Things (IoT) based services are getting a widespread expansion in all the directions and dimensions of the 21st century. The IoT based deployment involves an internet-connected sensor, mobiles, laptops, and other networking and computing de- vices. In most IoT based applications, the sensor collects the data and communicates it to the end-user via gateway device or fog device over a precarious internet channel. The attacker can use this open channel to capture the sensing device or the gateway device to collect the IoT data or control the IoT system. For a long time, numerous researchers are working towards designing the authentication mechanism for the sen- sor network to achieve reliable and computationally feasible security. For the resource constraint environment of the IoT, it is essential to design reliable, ecient, and secure authentication protocol. In this paper, we propose a novel approach of authentication in the IoT paradigm called a Level-Dependent Authentication(LDA). In the LDA protocol, we propose a security reliable and resource ecient key sharing mechanism in which users at level li can communicate with the sensor at level lj if and only if the level of user in the organizational hierarchy is lower or equal to the level of sensor deployment. We pro- vide a security analysis for the proposed LDA protocol using random oracle based games & widely accepted AVISPA tools. We prove mutual authentication for the proposed protocol using BAN logic. In this paper, we also discuss a comparative analysis of the proposed protocol with other existing IoT authentication systems based on communica- tion cost, computation cost, and security index. We provide an implementation for the proposed protocol using a globally adopted IoT protocol called MQTT protocol. Finally, we present the collected data related to the networking parameters like throughput and round trip delay.

Oblivious linear evaluation (OLE) is a fundamental building block in multi-party computation protocols. In OLE, a sender holds a description of an affine function $f_{\alpha,\beta}(z)=\alpha z+\beta$, the receiver holds an input $x$, and gets $\alpha x+\beta$ (where all computations are done over some field, or more generally, a ring). Vector OLE (VOLE) is a generalization where the sender has many affine functions and the receiver learns the evaluation of all of these functions on a single point $x$. The state-of-the-art semi-honest VOLE protocols generally fall into two groups. The first group relies on standard assumptions to achieve security but lacks in concrete efficiency. These constructions are mostly based on additively homomorphic encryption (AHE) and are classified as ``folklore". The second group relies on less standard assumptions, usually properties of sparse, random linear codes, but they manage to achieve concrete practical efficiency. In this work, we present a conceptually simple VOLE protocol that derives its security from a standard assumption, namely Ring Learning with Errors (RLWE), while still achieving concrete efficiency comparable to the fastest VOLE protocols from non-standard coding assumptions. Furthermore, our protocol admits a natural extension to batch OLE (BOLE), which is yet another variant of OLE that computes many OLEs in parallel.

Secure-channel establishment allows two endpoints to communicate confidentially and authentically. Since they hide all data sent across them, good or bad, secure channels are often subject to mass surveillance in the name of (inter)national security. Some protocols are constructed to allow easy data interception . Others are designed to preserve data privacy and are either subverted or prohibited to use without trapdoors. We introduce LIKE, a primitive that provides secure-channel establishment with an exceptional, session-specific opening mechanism. Designed for mobile communications, where an operator forwards messages between the endpoints, it can also be used in other settings. LIKE allows Alice and Bob to establish a secure channel with respect to n authorities. If the authorities all agree on the need for interception, they can ensure that the session key is retrieved. As long as at least one honest authority prohibits interception, the key remains secure; moreover LIKE is versatile with respect to who learns the key. Furthermore, we guarantee non-frameability: nobody can falsely incriminate a user of taking part in a conversation; and honest-operator: if the operator accepts a transcript as valid, then the key retrieved by the authorities is the key that Alice and Bob should compute. Experimental results show that our protocol can be efficiently implemented.

Ring signatures are a cryptographic primitive that allow a signer to anonymously sign messages on behalf of an ad-hoc group of $N$ potential signers (the so-called ring). This primitive has attracted significant research since its introduction by Rivest et al. (ASIACRYPT'01), but until recently, no construction was known that was both (i) compact, i.e., the signature size is sub-linear in $N$, and (ii) in the plain model, i.e., secure under standard hardness assumptions without requiring heuristic or setup assumptions. The first construction in this most desirable setting, where reducing trust in external parties is the primary goal, was only recently presented by Backes et al. (EUROCRYPT'19). An interesting generalization of ring signatures are $t$-out-of-$N$ ring signatures for $t\geq 1$, also known as threshold ring (thring) signatures (Bresson et al., CRYPTO'02). For threshold ring signatures, non-linkable sub-linear-size constructions are not even known under heuristic or setup assumptions. In this work, we propose the first sub-linear thring signatures and prove them secure in the plain model. While our constructions are inspired by the template underlying the Backes et al. construction, they require novel ideas and techniques. Our scheme is non-interactive, and has strong inter-signer anonymity, meaning that signers do not need to know the other signers that participate in a threshold signing. We then present a linkable counterpart to our non-linkable construction. Our thring signatures can easily be adapted to achieve the recently introduced notions of flexibility (Okamoto et al., EPRINT'18) as well as claimability and repudiability (Park and Sealfon, CRYPTO'19). (Th)Ring signatures and, in particular, their linkable versions have recently drawn significant attention in the field of privacy-friendly cryptocurrencies. We discuss applications that are enabled by our strong inter-signer anonymity, demonstrating that thring signatures are interesting from a practical perspective also.

A Diophantine equation is a multi-variate polynomial equation with integer coefficients, and it is satisfiable if it has a solution with all unknowns taking integer values. Davis, Putnam, Robinson and Matiyasevich showed that the general Diophantine satisfiability problem is undecidable (giving a negative answer to Hilbert’s tenth problem) but it is nevertheless possible to argue in zero-knowledge the knowledge of a solution, if a solution is known to a prover. We provide the first succinct honest-verifier zero-knowledge argument for the satisfiability of Diophantine equations with a communication complexity and a round complexity that grows logarithmically in the size of the polynomial equation. The security of our argument relies on standard assumptions on hidden-order groups. As the argument requires to commit to integers, we introduce a new integer-commitment scheme that has much smaller parameters than Damgard and Fujisaki’s scheme. We finally show how to succinctly argue knowledge of solutions to several NP-complete problems and cryptographic problems by encoding them as Diophantine equations.

This report deals with the problem of identifying the potential correlations between the observable power consumption of a digital circuit and its inputs, when the operating conditions of the circuit involve a logic hazard (also known as glitch). This problem is of utmost importance when the circuit is a cryptographic primitive that must ensure that secret input data (e.g., keys) does not leak. We present a universal algebra construction that allows to derive a set of artefacts from a digital circuit among which a conservative estimate of the Boolean expression that the circuit might leak as well as the extended input/output correlation matrix [1]. This allows the evaluation of the robustness against side channel attacks through a set of constructions that fall under the umbrella of robust probing security [2]. We believe that such a formalisation is well suited for CAD synthesis tools to help the design of more robust cryptographic primitives.

Bit permutation based block ciphers, like PRESENT and GIFT, are well-known for their extreme lightweightness in hardware implementation. However, designing such ciphers comes with one major challenge - to ensure strong cryptographic properties simply depending on the combination of three components, namely S-box, a bit permutation and a key addition function. Having a wrong combination of components could lead to weaknesses. In this article, we studied the interaction between these components, improved the theoretical security bound of GIFT and highlighted the potential pitfalls associated with a bit permutation based primitive design. We also conducted analysis on TRIFLE, a first-round candidate for the NIST lightweight cryptography competition, where our findings influenced the elimination of TRIFLE from second-round of the NIST competition. In particular, we showed that internal state bits of TRIFLE can be partially decrypted for a few rounds even without any knowledge of the key.

In the past decades, user authentication has been dominated by server-side password-based solutions that rely on "what users know". This approach is susceptible to breaches and phishing attacks, and poses usability challenges. As a result, the industry is gradually moving to biometric-based client-side solutions that do not store any secret information on servers. This shift necessitates the safe storage of biometric templates and private keys, which are used to generate tokens, on user devices. We propose a new generic framework called Biometric Enabled Threshold Authentication (BETA) to protect sensitive client-side information like biometric templates and cryptographic keys. Towards this, we formally introduce the notion of Fuzzy Threshold Tokenizer (FTS) where an initiator can use a "close" biometric measurement to generate an authentication token if at least $t$ (the threshold) devices participate. We require that the devices only talk to the initiator, and not to each other, to capture the way user devices are connected in the real world. We use the universal composability (UC) framework to model the security properties of FTS, including the unforgeability of tokens and the privacy of the biometric values (template and measurement), under a malicious adversary. We construct three protocols that meet our definition. Our first two protocols are general feasibility results that work for any distance function, any threshold $t$ and tolerate the maximal (i.e. $t-1$) amount of corruption. They are based on any two round UC-secure multi-party computation protocol in the standard model (with a CRS) and threshold fully homomorphic encryption, respectively. We show how to effectively use these primitives to build protocols in a constrained communication model with just four rounds of communication. For the third protocol, we consider inner-product based distance metrics (cosine similarity, Euclidean distance, etc.) specifically, motivated by the recent interest in its use for face recognition. We use Paillier encryption, efficient NIZKs for specific languages, and a simple garbled circuit to build an efficient protocol for the common case of $n=3$ devices with one compromised.

We consider threshold ring signatures (introduced by Bresson et al. [BSS02], where any t signers can sign a message while anonymizing themselves within a larger (size-n) group. The signature proves that t members of the group signed, without revealing anything else about their identities. Our contributions in this paper are two-fold. First, we strengthen existing definitions of threshold ring signatures in a natural way; we demand that a signer cannot be de-anonymized even by their fellow signers. This is crucial, since in applications where a signer's anonymity is important, we do not want anonymity to be compromised by a single insider. Our definitions demand non-interactive signing, which is important for anonymity, since truly anonymous interaction is difficult or impossible in many scenarios. Second, we give the first rigorous construction of a threshold ring signature with size independent of n, the number of users in the larger group. Instead, our signatures have size linear in t, the number of signers. This is also a very important contribution; signers should not have to choose between achieving their desired degree of anonymity (possibly very large n) and their need for communication efficiency.

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting--anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents ``sybil attacks'' (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. ``moderately hard functions'') introduced by Dwork and Naor (Crypto'92). Recent work by Garay et al (EuroCrypt'15) and Pass et al. (EuroCrypt'17) demonstrate that this protocol provably achieves consistency and liveness assuming a) honest players control a majority of the computational power in the network, b) the puzzle-difficulty is appropriately set as a function of the maximum network message delay and the total computational power of the network, and c) the computational puzzle is modeled as a random oracle. These works, however, leave open the question of how to set the puzzle difficulty in a setting where the computational power in the network is changing. Nakamoto's protocol indeed also includes a description of a difficutly update procedure. A recent work by Garay et al. (Crypto'17) indeed shows a variant of this difficulty adjustment procedure can be used to get a sound protocol as long as the computational power does not change too fast --- however, under two restrictions: 1) their analysis assumes that the attacker cannot delays network messages, and 2) the changes in computational power in the network changes are statically set (i.e., cannot be adaptively selected by the adversary). In this work, we show the same result but without these two restrictions, demonstrating the soundness of a (slightly different) difficulty update procedure, assuming only that the computational power in the network does not change too fast (as a function of the maximum network message delays); as an additional contribution, our analysis yields a tight bound on the ``chain quality'' of the protocol.

A common approach to bootstrapping a new cryptocurrency is an airdrop, an arrangement in which existing users give away currency to entice new users to join. But current airdrops offer no recipient privacy: they leak which recipients have claimed the funds, and this information is easily linked to off-chain identities. In this work, we address this issue by defining a private airdrop and describing concrete schemes for widely-used user credentials, such as those based on ECDSA and RSA. Our private airdrop for RSA builds upon a new zero-knowledge argument of knowledge of the factorization of a committed secret integer, which may be of independent interest. We also design a private genesis airdrop that efficiently sends private airdrops to millions of users at once. Finally, we implement and evaluate. Our fastest implementation takes 40--180 ms to generate and 3.7--10 ms to verify an RSA private airdrop signature. Signatures are 1.8--3.3 kiB depending on the security parameter.

Blockchain protocols based on variations of the longest-chain rule—whether following the proof-of-work paradigm or one of its alternatives—suffer from a fundamental latency barrier. This arises from the need to collect a sufficient number of blocks on top of a transaction-bearing block to guarantee the transaction’s stability while limiting the rate at which blocks can be created in order to prevent security-threatening forks. Our main result is a black-box security-amplifying combiner based on parallel composition of $m$ blockchains that achieves $\Theta(m)$-fold security amplification for conflict-free transactions or, equivalently, $\Theta(m)$-fold reduction in latency. Our construction breaks the latency barrier to achieve, for the first time, a ledger based purely on Nakamoto longest-chain consensus guaranteeing worst-case constant-time settlement for conflict-free transactions: settlement can be accelerated to a constant multiple of block propagation time with negligible error. Operationally, our construction shows how to view any family of blockchains as a unified, virtual ledger without requiring any coordination among the chains or any new protocol metadata. Users of the system have the option to inject a transaction into a single constituent blockchain or—if they desire accelerated settlement—all of the constituent blockchains. Our presentation and proofs introduce a new formalism for reasoning about blockchains, the dynamic ledger, and articulate our constructions as transformations of dynamic ledgers that amplify security. We also illustrate the versatility of this formalism by presenting robust-combiner constructions for blockchains that can protect against complete adversarial control of a minority of a family of blockchains.

Coercion resistance is one of the most important features of a secure voting procedure. Because of the properties such as transparency, decentralization, and non-repudiation, blockchain is a fundamental technology of great interest in its own right, and it also has large potential when integrated into many other areas. Here we propose a decentralized e-voting protocol that is coercion-resistant and vote-selling resistant, while being also completely transparent and not receipt-free. We prove the security of the protocol under the standard DDH assumption.

We present LotMint, a permissionless blockchain, with a purposely low set bar for Proof-of-Work (PoW) difficulty. Our objective is for personal computers, cloud virtual machines or containers, even mobile devices, and hopefully future IoT devices, to become the main, widely distributed, collectively much securer, fairer, more reliable and economically sustainable mining workforce for blockchains. An immediate question arises: how to prevent the permissionless network from being flooded of block dissemination traffic by a massive number of profit enthusiastic miners? We propose a novel notion of {\em Decentralized Clock/Time} (DC/DT) as global and logical clock/time which can be agreed upon as a consensus. Our construction of DC/DT practically uses distributed private clocks of the participation nodes. With DC/DT, a node upon creating or hearing a block can know how luckily short or unluckily long time for the block to have been mined and/or traveled through the network. They can ``time throttle'' a potentially large number of unluckily mined/travelled blocks. The luckier blocks passing through the time throttle are treated as time-tie forks with a volume being ``throttle diameter'' adjustably controlled not to congest the network. With the number of time-tie forks being manageable, it is then easy to break-tie elect a winner, or even to orderly queue a plural number of winners for a ``multi-core'' utilization of resource. We provide succinct and evident analyses of necessary properties for the LotMint blockchain including: decentralization, energy saving, safety, liveness, robustness, fairness, anti-denial-of-service, anti-sybil, anti-censorship, scaled-up transaction processing throughput and sped-up payment confirmation time.

To combat the ongoing Covid-19 pandemic, many new ways have been proposed on how to automate the process of finding infected people, also called contact tracing. A special focus was put on preserving the privacy of users. Bluetooth Low Energy (BLE) as base technology has the most promising properties, so this survey focuses on automated contact tracing techniques using BLE. We define multiple classes of methods and identify two major groups: systems that rely on a server for finding new infections and systems that distribute this process. Existing approaches are systematically classified regarding security and privacy criteria.

Persistent fault analysis (PFA) consists in guessing block cipher secret keys by biasing their substitution box. This paper improves the original attack of Zhang et al. on AES-128 presented at CHES 2018. By a thorough analysis, the exact probability distribution of the ciphertext (under a uniformly distributed plaintext) is derived, and the maximum likelihood key recovery estimator is computed exactly. Its expression is turned into an attack algorithm, which is shown to be twice more efficient in terms of number of required encryptions than the original attack of Zhang et al. This algorithm is also optimized from a computational complexity standpoint. In addition, our optimal attack is naturally amenable to key enumeration, which expedites full 16- bytes key extraction. Various tradeoffs between data and computational complexities are investigated.

Automated contract tracing aims at supporting manual contact tracing during pandemics by alerting users of encounters with infected people. There are currently many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized” ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly broadcast (using low energy Bluetooth) some values, and at the same time store (a function of) incoming messages broadcasted by users in their proximity. In the existing proposals one can trigger false positives on a massive scale by an “inverse-Sybil” attack, where a large number of devices (malicious users or hacked phones) pretend to be the same user, such that later, just a single person needs to be diagnosed (and allowed to upload) to trigger an alert for all users who were in proximity to any of this large group of devices. We propose the first protocols that do not succumb to such attacks assuming the devices involved in the attack do not constantly communicate, which we observe is a necessary assumption. The high level idea of the protocols is to derive the values to be broadcasted by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil attack will not be able to connect their respective chains and thus only one of them will be able to upload. Our protocols also achieve security against replay, belated replay, and one of them even against relay attacks.

In ICISC-05, and in the ePrint $2010/287$, Patarin claimed a lower bound on the number of $2q$ tuples of $n$-bit strings $(P_1, \ldots, P_{2q}) \in (\{0,1\}^{n})^{2q}$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda_i$ for $1 \leq i \leq q$ such that $P_1, P_2, \ldots$, $P_{2q}$ are distinct and $\lambda_i \in \{0,1\}^n \setminus \{0^n\}$. This result is known as {\em Mirror theory} and widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory.

While NIZK arguments in the CRS model are widely studied, the question of what happens when the CRS was subverted has received little attention. In ASIACRYPT 2016, Bellare, Fuchsbauer, and Scafuro showed the first negative and positive results in the case of NIZK, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero-knowledge at the same time. On the positive side, they constructed an involved sound and subversion-zero-knowledge (Sub-ZK) non-succinct NIZK argument for NP. We consider the practically very relevant case of zk-SNARKs. We make Groth's zk-SNARK for \textsc{Circuit-SAT} from EUROCRYPT 2016 computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We only require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for knowledge-sound and Sub-ZK SNARKs.

In ToSC 2017 Saha et al. demonstrated an interesting property of SHA3 based on higher-order vectorial derivatives which led to self-symmetry based distinguishers referred to as SymSum and bettered the complexity w.r.t the well-studied ZeroSum distinguisher by a factor of 4. This work attempts to take a fresh look at this distinguisher in the light of the linearization technique developed by Guo et al. in Asiacrypt 2016. It is observed that the efficiency of SymSum against ZeroSum drops from 4 to 2 for any number of rounds linearized. This is supported by theoretical proofs. SymSum augmented with linearization can penetrate up to two more rounds as against the classical version. In addition to that, one more round is extended by inversion technique on the final hash values. The combined approach leads to distinguishers up to 9 rounds of SHA3 variants with a complexity of only 264 which is better than the equivalent ZeroSum distinguisher by the factor of 2. To the best of our knowledge this is the best distinguisher available on this many rounds of SHA3.

Binary error LWE is the particular case of the learning with errors (LWE) problem in which errors are chosen in $\{0,1\}$. It has various cryptographic applications, and in particular, has been used to construct efficient encryption schemes for use in constrained devices. Arora and Ge showed that the problem can be solved in polynomial time given a number of samples quadratic in the dimension $n$. On the other hand, the problem is known to be as hard as standard LWE given only slightly more than $n$ samples. In this paper, we first examine more generally how the hardness of the problem varies with the number of available samples. Under standard heuristics on the Arora--Ge polynomial system, we show that, for any $\epsilon >0$, binary error LWE can be solved in polynomial time $n^{O(1/\epsilon)}$ given $\epsilon\cdot n^{2}$ samples. Similarly, it can be solved in subexponential time $2^{\tilde O(n^{1-\alpha})}$ given $n^{1+\alpha}$ samples, for $0<\alpha<1$. As a second contribution, we also generalize the binary error LWE to problem the case of a non-uniform error probability, and analyze the hardness of the non-uniform binary error LWE with respect to the error rate and the number of available samples. We show that, for any error rate $0 < p < 1$, non-uniform binary error LWE is also as hard as worst-case lattice problems provided that the number of samples is suitably restricted. This is a generalization of Micciancio and Peikert's hardness proof for uniform binary error LWE. Furthermore, we also discuss attacks on the problem when the number of available samples is linear but significantly larger than $n$, and show that for sufficiently low error rates, subexponential or even polynomial time attacks are possible.

This paper deals with Montgomery-friendly primes designed for the modular reduction algorithm of Montgomery. These numbers are scattered in the literature and their properties are partially exploited. We exhibit a large family of Montgomery-friendly primes which give rise to efficient modular reduction algorithms. We develop two main uses. The first one is dedicated directly to cryptography, in particular for isogeny based approaches and more generally to Elliptic Curves Cryptography. We suggest more appropriate finite fields and curves in terms of complexity for the recommended security levels, for both isogeny-based cryptography and ECC. The second use is purely arithmetic, and we propose families of alternative RNS bases. We show that, for dedicated architectures with word operators, we can reach, for a same or better complexity, larger RNS bases with Montgomery-friendly pairwise co-primes than the RNS bases generally used in the literature with Pseudo-Mersenne numbers. This is particularly interesting for modular arithmetic used in cryptography.

The share size of general secret-sharing schemes is poorly understood. The gap between the best known upper bound on the total share size per party of $2^{0.59n}$ (Applebaum and Nir, CRYPTO 2021) and the best known lower bound of $\Omega(n/\log n)$ (Csirmaz, J. of Cryptology 1997) is huge (where $n$ is the number of parties in the scheme). To gain some understanding on this problem, we study the share size of secret-sharing schemes of almost all access structures, i.e., of almost all collections of authorized sets. This is motivated by the fact that in complexity, many times almost all objects are hardest (e.g., most Boolean functions require exponential size circuits). All previous constructions of secret-sharing schemes were for the worst access structures (i.e., all access structures) or for specific families of access structures. We prove upper bounds on the share size for almost all access structures. We combine results on almost all monotone Boolean functions (Korshunov, Probl. Kibern. 1981) and a construction of (Liu and Vaikuntanathan, STOC 2018) and conclude that almost all access structures have a secret-sharing scheme with share size $2^{\tilde{O}(\sqrt{n})}$. We also study graph secret-sharing schemes. In these schemes, the parties are vertices of a graph and a set can reconstruct the secret if and only if it contains an edge. Again, for this family there is a huge gap between the upper bounds - $O(n/\log n)$ (Erdös and Pyber, Discrete Mathematics 1997) - and the lower bounds - $\Omega(\log n)$ (van Dijk, Des. Codes Crypto. 1995). We show that for almost all graphs, the share size of each party is $n^{o(1)}$. This result is achieved by using robust 2-server conditional disclosure of secrets protocols, a new primitive introduced and constructed in (Applebaum et al., STOC 2020), and the fact that the size of the maximal independent set in a random graph is small. Finally, using robust conditional disclosure of secrets protocols, we improve the total share size for all very dense graphs.

We build symmetric encryption schemes from a pseudorandom function/permutation with domain size $N$ which have very high security -- in terms of the amount of messages $q$ they can securely encrypt -- assuming the adversary has $S < N$ bits of memory. We aim to minimize the number of calls $k$ we make to the underlying primitive to achieve a certain $q$, or equivalently, to maximize the achievable $q$ for a given $k$. We target in particular $q \gg N$, in contrast to recent works (Jaeger and Tessaro, EUROCRYPT '19; Dinur, EUROCRYPT '20) which aim to beat the birthday barrier with one call when $S < \sqrt{N}$. Our first result gives new and explicit bounds for the Sample-then-Extract paradigm by Tessaro and Thiruvengadam (TCC '18). We show instantiations for which $q =\Omega((N/S)^{k})$. If $S < N^{1- \alpha}$, Thiruvengadam and Tessaro's weaker bounds only guarantee $q > N$ when $k = \Omega(\log N)$. In contrast, here, we show this is true already for $k = O(1/\alpha)$. We also consider a scheme by Bellare, Goldreich and Krawczyk (CRYPTO '99) which evaluates the primitive on $k$ independent random strings, and masks the message with the XOR of the outputs. Here, we show $q= \Omega((N/S)^{k/2})$, using new combinatorial bounds on the list-decodability of XOR codes which are of independent interest. We also study best-possible attacks against this construction.

Dark markets for share trading provide an important function in the financial services industry, however the operators of such markets are not operating in the dark; leaving the possibility open for the market operator to gain a market advantage. Multi-Party Computation (MPC) is a method to remove the need for such trusted third parties. In this paper we show how MPC can be used to implement such a dark market. Importantly we base our solution on the throughputs and algorithms needed in real markets. In particular we base our implementation on the Turquoise Plato market used by the London Stock Exchange.

We establish the optimal security threshold for the Bitcoin protocol in terms of adversarial hashing power, honest hashing power, and network delays. Specifically, we prove that the protocol is secure if $$r_a < \frac{1}{\Delta + 1/r_h}\; ,$$ where $r_h$ is the expected number of honest proof-of-work successes in unit time, $r_a$ is the expected number of adversarial successes, and no message is delayed by more than $\Delta$ time units. In this regime, the protocol guarantees consistency and liveness with exponentially decaying failure probabilities. Outside this region, the simple private chain attack prevents consensus. Our analysis immediately applies to any Nakamoto-style proof-of-work protocol; we also present the adaptations needed to apply it in the proof-of-stake setting, establishing a similar threshold there.

Thanks to relatively small public and secret keys, the Supersingular Isogeny Key Encapsulation (SIKE) protocol made it into the third evaluation round of the post-quantum standardization project of the National Institute of Standards and Technology (NIST). Even though a large body of research has been devoted to the efficient implementation of SIKE, its latency is still undesirably long for many real-world applications. Most existing implementations of the SIKE protocol use the Montgomery representation for the underlying field arithmetic since the corresponding reduction algorithm is considered the fastest method for performing multiple-precision modular reduction. In this paper, we propose a new data representation for supersingular isogeny-based Elliptic-Curve Cryptography (ECC), of which SIKE is a sub-class. This new representation enables significantly faster implementations of modular reduction than the Montgomery reduction, and also other finite-field arithmetic operations used in ECC can benefit from our data representation. We implemented all arithmetic operations in C using the proposed representation such that they have constant execution time and integrated them to the latest version of the SIKE software library. Using four different parameters sets, we benchmarked our design and the optimized generic implementation on a 2.6 GHz Intel Xeon E5-2690 processor. Our results show that, for the prime of SIKEp751, the proposed reduction algorithm is approximately 2.61 times faster than the currently best implementation of Montgomery reduction, and our representation also enables significantly better timings for other finite-field operations. Due to these improvements, we were able to achieve a speed-up by a factor of about 1.65, 2.03, 1.61, and 1.48 for SIKEp751, SIKEp610, SIKEp503, and SIKEp434, respectively, compared to state-of-the-art generic implementations.IKEp751, SIKEp610, SIKEp503, and SIKEp434, respectively, compared to state-of-the-art generic implementations.

Grain-128AEAD is a stream cipher supporting authenticated encryption with associated data, and it is currently in round 2 of the NIST lightweight crypto standardization process. In this paper we present and benchmark software implementations of the cipher, targeting constrained processors. The processors chosen are the 8-bit (AVR) and 16-bit (MSP) processors used in the FELICS-AEAD framework. Both high speed and small code size implementations are targeted, giving us in total 4 different implementations. Using the FELICS framework for benchmarking, we conclude that Grain-128AEAD is competitive to other algorithms currently included in the FELICS framework. Our detailed discussion regarding particular implementation tricks and choices can hopefully be of use for the community when considering optimizations for other ciphers.

In Time-Specific Signatures (TSS) parameterized by an integer $T\in\mathbb{N}$, a signer with a secret-key associated with a numerical value $t\in[0,T-1]$ can anonymously, i.e., without revealing $t$, sign a message under a numerical range $[L,R]$ such that $0\leq L \leq t\leq R\leq T-1$. An application of TSS is anonymous questionnaire, where each user associated with a numerical value such as age, date, salary, geographical position (represented by longitude and latitude) and etc., can anonymously fill in a questionnaire in an efficient manner. In this paper, we propose two \textit{polylogarithmically} efficient TSS constructions based on asymmetric pairing with groups of prime order, which achieve different characteristics in efficiency. In the first one based on a forward-secure signatures scheme concretely obtained from a hierarchical identity-based signatures scheme proposed by Chutterjee and Sarker (IJACT'13), size of the master public-key, size of a secret-key and size of a signature are asymptotically $\mathcal{O}(\log T)$, and size of the master secret-key is $\mathcal{O}(1)$. In the second one based on a wildcarded identity-based ring signatures scheme obtained as an instantiation of an attribute-based signatures scheme proposed by Sakai, Attrapadung and Hanaoka (PKC'16), the sizes are $\mathcal{O}(\log T)$, $\mathcal{O}(1)$, $\mathcal{O}(\log^2 T)$ and $\mathcal{O}(\log T)$, respectively.

Many attribute-based anonymous credential (ABC) schemes have been proposed allowing a user to prove the possession of some attributes, anonymously. They became more and more practical with, for the most recent papers, a constant-size credential to show a subset of attributes issued by a unique credential issuer. However, proving possession of attributes coming from $K$ different credential issuers usually requires $K$ independent credentials to be shown. Only attribute-based credential schemes from aggregate signatures can overcome this issue. In this paper, we propose new ABC schemes from aggregate signatures with randomizable tags. We consider malicious credential issuers, with adaptive corruptions and collusions with malicious users. Whereas our constructions only support selective disclosures of attributes, to remain compact, our approach significantly improves the complexity in both time and memory of the showing of multiple attributes: for the first time, the cost for the prover is (almost) independent of the number of attributes and the number of credential issuers. Whereas anonymous credentials require privacy of the user, we also propose the first schemes allowing traceability by a specific tracing authority.

At FSE 2017, Gaži et al. demonstrated a pseudorandom function (PRF) distinguisher (Gaži et al., ToSC 2016(2)) on PMAC with $ \Omega(\ell q^2/2^n) $ advantage, where $ q $, $ \ell $, and $ n $, denote the number of queries, maximum permissible query length (in terms of $ n $-bit blocks), and block size of the underlying block cipher. This, in combination with the upper bounds of $ O(\ell q^2/2^n) $ (Minematsu and Matsushima, FSE 2007) and $ O(q\sigma/2^n) $ (Nandi and Mandal, J. Mathematical Cryptology 2008(2)), resolved the long-standing problem of exact security of PMAC. Gaži et al. also showed that the dependency on $ \ell $ can be dropped (i.e. $ O(q^2/2^n) $ bound up to $ \ell \leq 2^{n/2} $) for a simplified version of PMAC, called sPMAC, by replacing the Gray code-based masking in PMAC with any $ 4 $-wise independent universal hash-based masking. Recently, Naito proposed another variant of PMAC with two powering-up maskings (Naito, ToSC 2019(2)) that achieves $ \ell $-free bound of $ O(q^2/2^n) $, provided $ \ell \leq 2^{n/2} $. In this work, we first identify a flaw in the analysis of Naito's PMAC variant that invalidates the security proof. Apparently, the flaw is not easy to fix under the existing proof setup. We then formulate an equivalent problem which must be solved in order to achieve $ \ell $-free security bounds for this variant. Second, we show that sPMAC achieves $ O(q^2/2^n) $ bound for a weaker notion of universality as compared to the earlier condition of $ 4 $-wise independence.

Side-channel analysis has seen rapid adoption of deep learning techniques over the past years. While many paper focus on designing efficient architectures, some works have proposed techniques to boost the efficiency of existing architectures. These include methods like data augmentation, oversampling, regularization etc. In this paper, we compare data augmentation and oversampling (particularly SMOTE and its variants) on public traces of two side-channel protected AES. The techniques are compared in both balanced and imbalanced classes setting, and we show that adopting SMOTE variants can boost the attack efficiency in general. Further, we report a successful key recovery on ASCAD(desync=100) with 180 traces, a 50% improvement over current state of the art.

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set in the collection has roughly half of its members $\delta$-close to the property and the others $\delta$-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed--Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any $\delta$ smaller than the Johnson/Guruswami-Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for $\delta$ smaller than the unique decoding radius. Concretely, if $\delta$ is smaller than half the minimal distance of an RS code $V\subset {\mathbb F}_q^n$, every affine space is either entirely $\delta$-close to the code, or alternatively at most an $(n/q)$-fraction of it is $\delta$-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed--Solomon codes (due to Berlekamp-Welch and Guruswami-Sudan) on a formal element of an affine space. This involves working with Reed-Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.

Recent years have seen various side-channel timing attacks demonstrated on both CPUs and GPUs, in diverse settings such as desktops, clouds, and mobile systems. These attacks observe events on different shared resources on the memory hierarchy from timing information, and then infer secret-dependent memory access pattern to retrieve the secret through statistical analysis. We generalize these attacks as memory-based side-channel attacks. In this paper, we propose a novel software countermeasure, MemPoline, against memory-based side-channel attacks. MemPoline hides the secret-dependent memory access pattern by moving sensitive data around randomly within a memory space. Compared to the prior oblivious RAM technology, MemPoline employs parameter-directed permutations to achieve randomness, which are significantly more efficient and yet provide similar security. Our countermeasure only requires modifying the source code, and has great advantages of being general - algorithm-agnostic, portable - independent of the underlying architecture, and compatible - a user-space approach that works for any operating system or hypervisor. We run a thorough evaluation of our countermeasure. We apply it to both AES, a symmetric cipher, and RSA, an asymmetric cipher. Both empirical results and theoretical analysis show that our countermeasure resists a series of existing memory-based side-channel attacks on CPUs and GPUs.

We define a new primitive that we call a somewhere statistically binding (SSB) commitment scheme, which is a generalization of dual-mode commitments but has similarities with SSB hash functions (Hubacek and Wichs, ITCS 2015) without local opening. In (existing) SSB hash functions, one can compute a hash of a vector v that is statistically binding in one coordinate of v. Meanwhile, in SSB commitment schemes, a commitment of a vector v is statistically binding in some coordinates of v and is statistically hiding in the other coordinates. The set of indices where binding holds is predetermined but known only to the commitment key generator. We show that the primitive can be instantiated by generalizing the succinct Extended Multi-Pedersen commitment scheme (González et al., Asiacrypt 2015). We further introduce the notion of functional SSB commitment schemes and, importantly, use it to get an efficient quasi-adaptive NIZK for arithmetic circuits and efficient oblivious database queries.

In this note, we review lattice-based public-key encryption with the keyword search against inside keyword guess attacks (IKGAs) proposed by Zhang \textit{et al}. in IEEE Transactions on Dependable and Secure Computing in 2021. We demonstrate that this scheme is insecure for IKGAs, although Zhang \textit{et al.} demonstrated a secure proof.

On 2 May 2019, during United Kingdom local elections, an e-voting trial was conducted in Gateshead, using a touch-screen end-to-end verifiable e-voting system. This was the first test of its kind in the United Kingdom, and it presented a case study to envisage the future of e-voting.

We give a construction of a non-interactive zero-knowledge (NIZK) argument for all NP languages based on a succinct non-interactive argument (SNARG) for all NP languages and a one-way function. The succinctness requirement for the SNARG is rather mild: We only require that the proof size be $|\pi|=\mathsf{poly}(\lambda)(|x|+|w|)^\delta$ for some constant $\delta<1$, where $|x|$ is the statement length, $|w|$ is the witness length, and $\lambda$ is the security parameter. Especially, we do not require anything about the efficiency of the verification. Based on this result, we also give a generic conversion from a SNARK to a zero-knowledge SNARG assuming the existence of one-way functions where SNARK is a SNARG with the knowledge-extractability. For this conversion, we require the SNARK to be fully succinct, i.e., the proof size is $\mathsf{poly}(\lambda)(|x|+|w|)^{o(1)}$. Before this work, such a conversion was only known if we additionally assume the existence of a NIZK. Along the way of obtaining our result, we give a generic compiler to upgrade a NIZK for all NP languages with non-adaptive zero-knowledge to one with adaptive zero-knowledge. Though this can be shown by carefully combining known results, to the best of our knowledge, no explicit proof of this generic conversion has been presented.

Data-sharing systems are often used to store sensitive data. Both academia and industry have proposed numerous solutions to protect user privacy and data integrity from a compromised server. Practical state-of-the-art solutions, however, use weak threat models based on centralized trust—they assume that part of the server will remain uncompromised, or that the adversary will not perform active attacks. We propose Ghostor, a data-sharing system that, using only decentralized trust, (1) hides user identities from the server, and (2) allows users to detect server-side integrity violations. To achieve (1), Ghostor avoids keeping any per-user state at the server, requiring us to redesign the system to avoid common paradigms like per-user authentication and user-specific mailboxes. To achieve (2), Ghostor develops a technique called verifiable anonymous history. Ghostor leverages a blockchain rarely, publishing only a single hash to the blockchain for the entire system once every epoch. We measured that Ghostor incurs a 4–5x throughput overhead compared to an insecure baseline. Although significant, Ghostor's overhead may be worth it for security- and privacy-sensitive applications.

Oblivious transfer (OT) is a fundamental problem in cryptography where it is required that a sender transfers one of potentially many pieces of information to a receiver and at the same time remains oblivious as to which piece has been transferred. After its introduction back in 1981 by Rabin, some more useful variations of OT appeared in the literature such as $OT^1_2$, $OT^1_n$, and $OT^k_n$. In 2015, a very simple and efficient OT protocol was proposed by Chou and Orlandi. Later, Hauck and Loss proposed an improved protocol and proved it to be fully UC-secure under the CDH assumption. Our goal in this paper is to extend the results of Hauck and Loss and propose a simple generic construction to build $OT^1_2$ and in general $OT^1_n$. The machinery we employ is homomorphic encryption. We instantiate our construction with some well known homomorphic encryption schemes such as RSA, Paillier, and NTRU to obtain concrete OT protocols. We further provide the details of the proof of the UC-security of our generic construction.

We construct efficient ring signatures from isogeny and lattice assumptions. Our ring signatures are based on a logarithmic OR proof for group actions. We then instantiate this group action by either the CSIDH group action or an MLWE-based group action to obtain our isogeny-based or lattice-based ring signature scheme respectively. Even though this OR proof has a binary challenge space and therefore needs to be repeated a linear number of times, the size of our ring signatures is small and scales better with the ring size N than previously known post-quantum ring signatures. We also construct linkable ring signatures that are almost as efficient as the non-linkable variant. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known logarithmic post-quantum ring signatures, but is relatively slow (e.g. 5.5 KB signatures and 79 s signing time for rings with 8 members). In comparison, our lattice-based construction is much faster, but has larger signatures (e.g. 30 KB signatures and 90 ms signing time for the same ring size). For small ring sizes our lattice-based ring signatures are slightly larger than state-of-the-art schemes, but they are smaller for ring sizes larger than $N \approx 1024$.

In this paper we study two-round key-alternating block ciphers with round function $f(x)=x^{(2^t+1)2^s},$ where $t,s$ are positive integers. An algorithm to compute the distribution weight with respect to input and output masks is described. In the case $t=1$ the correlation distributions in dependence on input and output masks are completely determined for arbitrary pairs of masks. We investigate with more details the case $f(x)=x^3$ and fully derive and classify the distributions, proving that there are only 5 possible values for the correlation for any pair of masks.

In this paper we present ALBATROSS, a family of multiparty randomness generation protocols with guaranteed output delivery and public verification that allows to trade off corruption tolerance for a much improved amortized computational complexity. Our basic stand alone protocol is based on publicly verifiable secret sharing (PVSS) and is secure under in the random oracle model under the decisional Diffie-Hellman (DDH) hardness assumption. We also address the important issue of constructing Universally Composable randomness beacons, showing two UC versions of Albatross: one based on simple UC NIZKs and another one based on novel efficient ``designated verifier'' homomorphic commitments. Interestingly this latter version can be instantiated from a global random oracle under the weaker Computational Diffie-Hellman (CDH) assumption. An execution of ALBATROSS with $n$ parties, out of which up to $t=(1/2-\epsilon)\cdot n$ are corrupt for a constant $\epsilon>0$, generates $\Theta(n^2)$ uniformly random values, requiring in the worst case an amortized cost per party of $\Theta(\log n)$ exponentiations per random value. We significantly improve on the SCRAPE protocol (Cascudo and David, ACNS 17), which required $\Theta(n^2)$ exponentiations per party to generate one uniformly random value. This is mainly achieved via two techniques: first, the use of packed Shamir secret sharing for the PVSS; second, the use of linear $t$-resilient functions (computed via a Fast Fourier Transform-based algorithm) to improve the randomness extraction.

A blockchain is designed to be a self-sufficient decentralised ledger: a peer verifying the validity of past transactions only needs to download the blockchain (the ledger) and nothing else. However, it might be of interest to make two different blockchains interoperable, i.e., to allow one to transmit information from one blockchain to another blockchain. In this paper, we give a formalisation of this problem, and we prove that blockchain interoperability is impossible according to the classical definition of a blockchain. Under a weaker definition of blockchain, we demonstrate that two blockchains are interoperable is equivalent to creating a `2-in-1' blockchain containing both ledgers, thus limiting the theoretical interest of making interoperable blockchains in the first place. We also observe that all practical existing interoperable blockchain frameworks work indeed by exchanging already created tokens between two blockchains and not by offering the possibility to transfer tokens from one blockchain to another one, which implies a modification of the balance of total created tokens on both blockchains. It confirms that having interoperability is only possible by creating a `2-in-1' blockchain containing both ledgers.

The distributed ledger technology has been widely hailed as the break- through technology. It has realised a great number of application scenarios, and improved workflow of many domains. Nonetheless, there remain a few major concerns in adopting and deploying the distributed ledger technology at scale. In this white paper, we tackle two of them, namely the throughput scalability and confidentiality protection for transactions. We learn from the existing body of research, and build a scale-out blockchain plat- form that champions privacy called RVChain. RVChain takes advantage of trusted execution environment to offer confidentiality protection for transactions, and scale the throughput of the network in proportion with the number of network participants by supporting parallel shadow chains.

In this paper we describe the design components of the heterogenous multi-chain protocol Polkadot and explain how these components help Polkadot address some of the existing shortcomings of blockchain technologies. At present, a vast number of blockchain projects have been introduced and employed with various features that are not necessarily designed to work with each other. This makes it difficult for users to utilise a large number of applications on different blockchain projects. Moreover, with the increase in number of projects the security that each one is providing individually becomes weaker. Polkadot aims to provide a scalable and interoperable framework for multiple chains with pooled security that is achieved by the collection of components described in this paper.

Grover search algorithm reduces the security level of symmetric key cryptography with $n$-bit secret key to $O(2^{n/2})$. In order to evaluate the Grover search algorithm, the target block cipher should be implemented in quantum circuits. Recently, many research works evaluated required quantum resources of AES block ciphers by optimizing the expensive substitute layer. However, only few works devoted to ARX-based lightweight block ciphers, which are active research area. In this paper, we present optimized implementations of SPECK 32/64 and SPECK 64/128 block ciphers for quantum computers. To the best of our knowledge, this is the first implementation of SPECK in quantum circuits. Primitive operations, including addition, rotation, and exclusive-or, for SPECK block cipher are finely optimized to achieve the optimal quantum circuit, in terms of qubits, Toffoli gate, CNOT gate, and X gate. The proposed method can be applied to other ARX-based lightweight block ciphers, such as LEA, HIGHT and CHAM block ciphers.

An indistinguishability obfuscator is a probabilistic polynomial-time algorithm that takes a circuit as input and outputs a new circuit that has the same functionality as the input circuit, such that for any two circuits of the same size that compute the same function, the outputs of the indistinguishability obfuscator are indistinguishable. Here, we study schemes for indistinguishability obfuscation for quantum circuits. We present two definitions for indistinguishability obfuscation: in our first definition (qiO) the outputs of the obfuscator are required to be indistinguishable if the input circuits are perfectly equivalent, while in our second definition (qiOD), the outputs are required to be indistinguishable as long as the input circuits are approximately equivalent with respect to a pseudo-distance D. Our main results provide (1) a computationally-secure scheme for qiO where the size of the output of the obfuscator is exponential in the number of non-Clifford (T gates), which means that the construction is efficient as long as the number of T gates is logarithmic in the circuit size and (2)a statistically-secure qiOD, for circuits that are close to the kth level of the Gottesman-Chuang hierarchy (with respect to D); this construction is efficient as long as k is small and fixed.

We introduce a new primitive named Delay Encryption, and give an efficient instantation based on isogenies of supersingular curves and pairings. Delay Encryption is related to Time-lock Puzzles and Verifiable Delay Functions, and can be roughly described as ``time-lock identity based encryption''. It has several applications in distributed protocols, such as sealed bid Vickrey auctions and electronic voting. We give an instantiation of Delay Encryption by modifying Boneh and Frankiln's IBE scheme, where we replace the master secret key by a long chain of isogenies, as in the isogeny VDF of De Feo, Masson, Petit and Sanso. Similarly to the isogeny-based VDF, our Delay Encryption requires a trusted setup before parameters can be safely used; our trusted setup is identical to that of the VDF, thus the same parameters can be generated once and shared for many executions of both protocols, with possibly different delay parameters. We also discuss several topics around delay protocols based on isogenies that were left untreated by De Feo et al., namely: distributed trusted setup, watermarking, and implementation issues.

Flush based cache attacks like Flush+Reload and Flush+Flush are one of the highly effective cache attacks. In fact, the Flush+Flush attack is stealthy too. Most of the flush based attacks provide high accuracy in controlled environments where attacker and victim are the only two processes that are running on a system by sharing OS pages. However, we observe that these attacks lose their effectiveness (prone to low accuracy) on a noisy multi-core system where co-running applications run along with the attacker and the victim. Two root causes for the varying accuracy of flush based attacks are: (i) the dynamic nature of core frequencies that fluctuate depending on the system load, and (ii) the relative placement of victim and attacker threads in the processor (same logical core, same physical core, different physical cores). The variation in the processor frequencies and placement of threads affect one of the critical attack steps (the cache latency calibration step as the latency threshold set to distinguish a cache hit from a miss becomes inaccurate). We propose a set of refinements (DABANGG refinements) to make existing flush attacks resilient to frequency changes and thread placement in the processor, and therefore system noise. We propose refinements to pre-attack and attack steps and make it conscious about the latency change. We evaluate DABANGG-enabled Flush+Reload and Flush+Flush attacks (DABANGG+Flush+Reload and DABANGG+Flush+Flush, respectively) against the standard Flush+Reload and Flush+Flush attacks across four scenarios for eight different combinations of system noise capturing different levels of compute, memory, and I/O noise intensities: (i) a side-channel attack based on user input (single-character and multi-character key-logging), (ii) a side-channel on AES, (iii) a covert-channel, and a (iv) transient execution attack in the form the Spectre attack. For all the scenarios, DABANGG+Flush+Reload and DABANGG+Flush+Flush outperform the standard Flush+Reload and Flush+Flush attacks in terms of F1-score and accuracy.

Protocols for secure multi-party computation are commonly composed of different sub-protocols, combining techniques such as homomorphic encryption, secret or Boolean sharing, and garbled circuits. In this paper, we design a new class of multi-party computation protocols which themselves are composed out of two-party protocols. We integrate both types of compositions, compositions of fully homomorphic encryption and garbled circuits with compositions of multi-party protocols from two-party protocols. As a result, we can construct communication-efficient protocols for special problems. Furthermore, we show how to efficiently ensure the security of composed protocols against malicious adversaries by proving in zero-knowledge that conversions between individual techniques are correct. To demonstrate the usefulness of this approach, we give an example scheme for private set analytics, i.e., private set disjointness. This scheme enjoys lower communication complexity than a solution based on generic multi-party computation and lower computation cost than fully homomorphic encryption. So, our design is more suitable for deployments in wide-area networks, such as the Internet, with many participants or problems with circuits of moderate or high multiplicative depth.

Oblivious Linear Evaluation (OLE) is the arithmetic analogue of the well-know oblivious transfer primitive. It allows a sender, holding an affine function $f(x)=a+bx$ over a finite field or ring, to let a receiver learn $f(w)$ for a $w$ of the receiver's choice. In terms of security, the sender remains oblivious of the receiver's input $w$, whereas the receiver learns nothing beyond $f(w)$ about $f$. In recent years, OLE has emerged as an essential building block to construct efficient, reusable and maliciously-secure two-party computation. In this work, we present efficient two-round protocols for OLE over large fields based on the Learning with Errors (LWE) assumption, providing a full arithmetic generalization of the oblivious transfer protocol of Peikert, Vaikuntanathan and Waters (CRYPTO 2008). At the technical core of our work is a novel extraction technique which allows to determine if a non-trivial multiple of some vector is close to a $q$-ary lattice.

Implementing cryptographic functions securely in the presence of physical adversaries is still a challenge although a lion's share of research in the physical security domain has been put in development of countermeasures. Among several protection schemes, masking has absorbed the most attention of research in both academic and industrial communities, due to its theoretical foundation allowing to provide proofs or model the achieved security level. In return, masking schemes are difficult to implement as the implementation process often is manual, complex, and error-prone. This motivated the need for formal verification tools that allow the designers and engineers to analyze and verify the designs before manufacturing. In this work, we present a new framework to analyze and verify masked implementations against various security notions using different security models as reference. In particular, our framework - which directly processes the resulting gate-level netlist of a hardware synthesis - particularly relies on Reduced Ordered Binary Decision Diagrams (ROBDDs) and the concept of statistical independence of probability distributions. Compared to existing tools, our framework captivates due to its simplicity, accuracy, and functionality while still having a reasonable efficiency for many applications and common use-cases.

SIDH is a post-quantum key exchange algorithm based on the presumed difficulty of finding isogenies between supersingular elliptic curves. However, SIDH and related cryptosystems also reveal additional information: the restriction of a secret isogeny to a subgroup of the curve (torsion-point information). Petit [30] was the first to demonstrate that torsion-point information could noticeably lower the difficulty of finding secret isogenies. In particular, Petit showed that "overstretched" parameterizations of SIDH could be broken in polynomial time. However, this did not impact the security of any cryptosystems proposed in the literature. The contribution of this paper is twofold: First, we strengthen the techniques of [30] by exploiting additional information coming from a dual and a Frobenius isogeny. This extends the impact of torsion-point attacks considerably. In particular, our techniques yield a classical attack that completely breaks the n-party group key exchange of [2], first introduced as GSIDH in [16], for 6 parties or more, and a quantum attack for 3 parties or more that improves on the best known asymptotic complexity. We also provide a Magma implementation of our attack for 6 parties. We give the full range of parameters for which our attacks apply. Second, we construct SIDH variants designed to be weak against our attacks; this includes backdoor choices of starting curve, as well as backdoor choices of base-field prime. We stress that our results do not degrade the security of, or reveal any weakness in, the NIST submission SIKE [19].

Search for the right pairs of inputs in difference-based distinguishers is an important task for the experimental verification of the distinguishers in symmetric-key ciphers. In this paper, we develop an MILP-based approach to verify the possibility of difference-based distinguishers and extract the right pairs. We apply the proposed method to some presented difference-based trails (Related-Key Differentials (RKD), Rotational-XOR (RX)) of block ciphers \texttt{SIMECK}, and \texttt{SPECK}. As a result, we show that some of the reported RX-trails of \texttt{SIMECK} and \texttt{SPECK} are incompatible, i.e. there are no right pairs that follow the expected propagation of the differences for the trail. Also, for compatible trails, the proposed approach can efficiently speed up the search process of finding the exact value of a weak-key from the target weak-key space. For example, in one of the reported 14-round RX trails of \texttt{SPECK}, the probability of a key pair to be a weak-key is $2^{-94.91}$ when the whole key space is $2^{96}$; our method can find a key pair for it in a comparatively short time. It is worth noting that it was impossible to find this key pair using a traditional search. As another result, we apply the proposed method %and consider a search strategy for the framework of to \texttt{SPECK} block cipher, to construct longer related-key differential trails of \texttt{SPECK} which we could reach 15, 16, 17, and 19 rounds for \texttt{SPECK32/64}, \texttt{SPECK48/96}, \texttt{SPECK64/128}, and \texttt{SPECK128/256}, respectively. It should be compared with the best previous results which are 12, 15, 15, and 20 rounds, respectively, that both attacks work for a certain weak key class. It should be also considered as an improvement over the reported result of rotational XOR cryptanalysis on \texttt{SPECK}.

We consider the problem of recovering the entries of diagonal matrices $\{U_a\}_a$ for $a = 1,\ldots,t$ from multiple ``incomplete'' samples $\{W_a\}_a$ of the form $W_a=PU_aQ$, where $P$ and $Q$ are unknown matrices of low rank. We devise practical algorithms for this problem depending on the ranks of $P$ and $Q$. This problem finds its motivation in cryptanalysis: we show how to significantly improve previous algorithms for solving the approximate common divisor problem and breaking CLT13 cryptographic multilinear maps.

The COVID-19 pandemic is a severe threat to both lives and economics throughout the world. Advanced information technology can play an important role to win this war against this invisible enemy. The most effective way to fight COVID-19 is quarantining infected people and identifying their contacts. Recently, quite a few Bluetooth-based contact tracing proposals have been proposed to identify who has come into contact with infected people. The success of a contact tracing system depends on multiple factors, including security and privacy features, simplicity and user-friendliness etc. More importantly, it should help the health authority to effectively enforce contact tracing, so as to control spreading of the vital virus as soon as possible. However, current proposals are either susceptible to security and privacy attacks, or expensive in computation and/or communication costs. In this paper, we propose ContactChaser, a simple but effective contact tracing scheme based on group signature, to achieve strong security and privacy protection for users. ContactChaser only requires a health authority to issue group private keys to users for only once, without frequently updating keys with the authority. It helps the authority to find out the close contacts of infected people, but just leaks the minimum information necessary for contact tracing to the health authority. Specially, the contact relationship is protect against the authority, which only knows the close contacts of infected people. ContactChaser is able to prevent most attacks, especially relay and replay attacks, so that it can effectively avoid false alerts and reduce unreported contacts. We give a detailed analysis of ContactChaser’s security and privacy properties as well as its performance. It is expected ContactChaser can contribute to the design and development of contact tracing schemes.

This paper formulates, and studies, the problem of property transference in dual-mode NIZKs. We say that a property P (such as soundness, ZK or WI) transfers, if, one of the modes having P allows us to prove that the other mode has the computational analogue of P, as a consequence of nothing but the indistinguishability of the CRSs in the two modes. Our most interesting finding is negative; we show by counter-example that the form of soundness that seems most important for applications fails to transfer. On the positive side, we develop a general framework that allows us to show that zero knowledge, witness indistinguishability, extractability and weaker forms of soundness do transfer. Our treatment covers conventional, designated-verifier and designated-prover NIZKs in a unified way.

In this paper, we present a key exchange protocol in which Alice and Bob have secret keys given by quadric surfaces embedded in a large ambient space by means of the Veronese embedding and public keys given by hyperplanes containing the embedded quadrics. Both of them reconstruct the isomorphism class of the intersection which is a curve of genus 1, which is uniquely determined by the j-invariant. An eavesdropper, to find this j-invariant, has to solve problems which are conjecturally quantum resistant.

This paper will outline, for the first time, exactly how the ITM Attack (a linkability attack against shielded transactions) works against Zcash Protocol and how Hush is the first cryptocoin with a defensive mitigation against it, called ”Sietch ”. Sietch is already running live in production and undergoing rounds of improvement from expert feedback. This is not an academic paper about pipedreams. It describes production code and networks. We begin with a literature review of all known metadata attack methods that can be used against Zcash Protocol blockchains. This includes their estimated attack costs and threat model. This paper then describes the ”ITM Attack” which is a specific instance of a new class of metadata attacks against blockchains which the author describes as Metaverse Metadata Attacks . The paper then explains Sietch in detail, which was a response to these new attacks. We hope this new knowledge and theory helps cryptocoins increase their defenses against very well-funded adversaries including nation states and chain analysis companies. A few other new privacy issues and metadata attacks against Zcash Protocol coins will also be enumerated for the first time publicly. The ideas in this paper apply to all cryptocoins which utilize transaction graphs, which is to say just about all known coins. Specifically, the Metaverse Metadata class of attacks is applicable to all Bitcoin source code forks (including Dash, Verge, Zerocoin and their forks), CryptoNote Protocol coins (Monero and friends) and MimbleWimble Protocol (Grin, Beam, etc) coins but these will not be addressed here other than a high-level description of how to apply these methods to those chains. In privacy zdust we trust. If dust can attack us, dust can protect us. – Sietch Mottos

Blockchains systems evolve in complex environments that mix classical patterns of faults (e.g crash faults, transient faults, Byzantine faults, churn) with selfish, rational or irrational behaviors typical to economical systems. In this paper we propose a game theoretical framework in order to formally characterize the robustness of blockchains systems in terms of resilience to rational deviations and immunity to Byzantine behaviors. Our framework includes necessary and sufficient conditions for checking the immunity and resilience of games and a new technique for composing games that preserves the robustness of individual games. We prove the practical interest of our formal framework by characterizing the robustness of three different protocols popular in blockchain systems: a HTLC-based payment scheme (a.k.a. Lightning Network), a side-chain protocol and a cross-chain swap protocol.

In this short note, we address a common misconception at the interface of probability theory and public-key cryptography.

We show it is possible to build an RSA-type cryptosystem by utilizing \textit{probable primes to base 2} numbers. Our modulus $N$ is the product $n\cdot m$ of such numbers (so here both prime and some composite, e.g. Carmichael or Fermat, numbers are acceptable) instead of prime numbers. Moreover, we require for $n$ and $m$ to be co-prime only, and so we don't have to worry about whether any of the numbers $n, m$ is composite or not. The encryption and decryption processes are similar as those in the RSA. Hence, in this cryptosystem we may apply the above kind of numbers of arbitrary length being still sure that the system works well. The price for that is not so high: the size of a message $M$ (as a number) permitted by the new system must be smaller than log (in base 2) of $n\cdot m$. The proposed cryptosystem can be applied in the case the numbers $n,m$ are 'sufficiently large' for a user, or as a completion of the classical RSA if $m,n$ are probable primes but possibly not prime, or in a 'secret sharing'-type cryptosystem. The numbers $n,m$ can be also taken from a narrower class of probable primes to base 2 numbers, e.g., Euler, or strong, or Baillie-PSW.

Private Set Intersection (PSI) enables two parties, each holding a private set to securely compute their intersection without revealing other information. This paper considers settings of secure statistical computations over PSI, where both parties hold sets containing identifiers with one of the parties having an additional positive integer value associated with each of the identifiers in her set. The main objective is to securely compute some desired statistics of the associated values for which its corresponding identifiers occur in the intersection of the two sets. This is achieved without revealing the identifiers of the set intersection. In this paper, we present protocols which enable the secure computations of statistical functions over PSI, which we collectively termed PSI-Stats. Implementations of our constructions are also carried out based on simulated datasets as well as on actual datasets in the business use cases that we defined, in order to demonstrate practicality of our solution. PSI-Stats incurs 5x less monetary cost compared to the current state-of-the-art circuit-based PSI approach due to Pinkas et al. (EUROCRYPT'19). Our solution is more tailored towards business applications where monetary cost is the primary consideration.

Updatable encryption schemes allow for key rotation on ciphertexts. A client outsourcing storage of encrypted data to a cloud server can change its encryption key. The cloud server can update the stored ciphertexts to the new key using only a token provided by the client. This paper solves two open problems in updatable encryption, that of uni-directional vs. bi-directional updates, and post-quantum security. The main result in this paper is to analyze the security notions based on uni- and bi-directional updates. Surprisingly, we prove that uni- and bi-directional variants of each security notion are equivalent. The second result in this paper is to provide a new and efficient updatable encryption scheme based on the Decisional Learning with Error assumption. This gives us post-quantum security. Our scheme is bi-directional, but because of our main result, this is sufficient.

The concept of quantum bit commitment was introduced in the early 1980s for the purpose of basing bit commitments solely on principles of quantum theory. Unfortunately, such unconditional quantum bit commitments still turn out to be impossible. As a compromise like in classical cryptography, Dumais et al. [DMS00] introduce the conditional quantum bit commitments that additionally rely on complexity assumptions. However, in contrast to classical bit commitments which are widely used in classical cryptography, up until now there is relatively little work towards studying the application of quantum bit commitments in quantum cryptography. This may be partly due to the well-known weakness of the general quantum binding that comes from the possible superposition attack of the sender of quantum commitments, making it unclear whether quantum commitments could be useful in quantum cryptography. In this work, following Yan et al. [YWLQ15] we continue studying using (canonical non-interactive) perfectly/statistically-binding quantum bit commitments as the drop-in replacement of classical bit commitments in some well-known constructions. Specifically, we show that the (quantum) security can still be established for zero-knowledge proof, oblivious transfer, and proof-of-knowledge. In spite of this, we stress that the corresponding security analyses are by no means trivial extensions of their classical analyses; new techniques are needed to handle possible superposition attacks by the cheating sender of quantum bit commitments. Since (canonical non-interactive) statistically-binding quantum bit commitments can be constructed from quantum-secure one-way functions, we hope using them (as opposed to classical commitments) in cryptographic constructions can reduce the round complexity and weaken the complexity assumption simultaneously.