## All papers (19210 results)

Last updated:  2022-12-06
Secret Key Recovery Attacks on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber
Linus Backlund, Kalle Ngo, Joel Gärtner, and Elena Dubrova
Shuffling is a well-known countermeasure against side-channel analysis. It typically uses the Fisher-Yates (FY) algorithm to generate a random permutation which is then utilized as the loop iterator to index the processing of the variables inside the loop. The processing order is scrambled as a result, making side-channel analysis more difficult. Recently, a side-channel attack on a masked and shuffled implementation of Saber requiring 61,680 power traces to extract the secret key was reported. In this paper, we present an attack that can recover the secret key of Saber from 4,608 traces. The key idea behind the 13-fold improvement is to recover FY indexes directly, rather than by extracting the message Hamming weight and bit flipping, as in the previous attack. We capture a power trace during the execution of the decapsulation algorithm for a given ciphertext, recover FY indexes 0 and 255, and extract the corresponding two message bits. Then, we modify the ciphertext to cyclically rotate the message, capture a power trace, and extract the next two message bits with FY indexes 0 and 255. In this way, all message bits can be extracted. By recovering messages contained in k ∗ l chosen ciphertexts constructed using a new method based on error-correcting codes with length l, where k is the security level, we recover the long term secret key. To demonstrate the generality of the presented approach, we also recover the secret key from a masked and shuffled implementation of CRYSTALS-Kyber, which NIST recently selected as a new public-key encryption and key-establishment algorithm to be standardized.
Last updated:  2022-12-06
TokenWeaver: Privacy Preserving and Post-Compromise Secure Attestation
Cas Cremers, Charlie Jacomme, and Eyal Ronen
Modern attestation based on Trusted Execution Environments (TEEs) can significantly reduce the risk of secret compromise by attackers, while allowing users to authenticate across various services. However, this has also made TEEs a high-value attack target, driving an arms race between novel compromise attacks and continuous TEEs updates. Ideally, we would like to ensure that we achieve Post-Compromise Security (PCS): even after a compromise, we can update the TEE into a secure state. However, at the same time, we would like the privacy of users to be respected, preventing providers (such as Intel, Google, or Samsung) or services from tracking users. In this work, we develop TokenWeaver, the first privacy-preserving post-compromise secure attestation method with automated formal proofs for its core properties. We base our construction on weaving together two types of token chains, one of which is linkable and the other is unlinkable. We provide the full formal models, including protocol, security properties, and proofs for reproducibility, as well as a proof-of-concept implementation in python that shows the simplicity and applicability of our solution.
Last updated:  2022-12-06
Private Re-Randomization for Module LWE and Applications to Quasi-Optimal ZK-SNARKs
Ron Steinfeld, Amin Sakzad, Muhammed F. Esgin, and Veronika Kuchta
We introduce the first candidate lattice-based Designated Verifier (DV) ZK-SNARK protocol with \emph{quasi-optimal proof length} (quasi-linear in the security/privacy parameter), avoiding the use of the exponential smudging technique. Our ZK-SNARK also achieves significant improvements in proof length in practice, with proofs length below $6$ KB for 128-bit security/privacy level. Our main technical result is a new regularity theorem for private' re-randomization of Module LWE (MLWE) samples using discrete Gaussian randomization vectors, also known as a lattice-based leftover hash lemma with leakage, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter. To obtain this result, we obtain bounds on the smoothing parameter of an intersection of a random $q$-ary SIS module lattice, Gadget SIS module lattice, and Gaussian orthogonal module lattice over standard power of 2 cyclotomic rings, and a bound on the minimum of module gadget lattices. We then introduce a new candidate \emph{linear-only} homomorphic encryption scheme called Module Half-GSW (HGSW), which is a variant of the GSW somewhat homomorphic encryption scheme over modules, and apply our regularity theorem to provide smudging-free circuit-private homomorphic linear operations for Module HGSW.
Last updated:  2022-12-05
Efficient Zero-Knowledge Arguments for Some Matrix Relations over Ring and Non-malleable Enhancement
Yuan Tian
Various matrix relations widely appeared in data-intensive computations, as a result their zero-knowledge proofs/arguments (ZKP/ZKA) are naturally required in large-scale private computing applications. In the first part of this paper, we concretely establish efficient zero-knowledge arguments for linear matrix relation AU = B and bilinear relation UQV = Y over the residue ring Zm with logarithmic message complexity. We take a direct, matrix-oriented (rather than vector-oriented in usual) approach to such establishments on basis of the elegant commitment scheme over the ring recently established by Attema et al[16]. The constructed protocols are public coin and in c.r.s paradigm (c.r.s used only as the public-key of the commitment scheme), suitable for any size matrices and outperform the protocols constructed in usual approach when number of columns > log(number of rows) with significantly smaller c.r.s., fewer rounds and lower message complexity, particularly for large-size squares. The on-line computational complexity is almost the same for both approaches. In the second part, on basis of the simulation-sound tag-based trapdoor commitment schemes we establish a general compiler to transform any public coin proof/argument protocol into the one which is concurrently non-malleable with unchanged number of rounds, properly increased message and computational complexity. Such enhanced protocols, e.g., the versions compiled from those constructed in the first part of this work, can run in parallel environment while keeping all their security properties, particularly resisting man-in-the-middle attacks.
Last updated:  2022-12-05
Funshade: Functional Secret Sharing for Two-Party Secure Thresholded Distance Evaluation
Alberto Ibarrondo, Hervé Chabanne, and Melek Önen
We propose a novel privacy-preserving, two-party computation of various distance metrics (e.g., Hamming distance, Scalar Product) followed by a comparison with a fixed threshold, which is known as one of the most useful and popular building blocks for many different applications including machine learning, biometric matching, etc. Our solution builds upon recent advances in functional secret sharing and makes use of an optimized version of arithmetic secret sharing. Thanks to this combination, our new solution named Funshade is the first to require only one round of communication and two ring elements of communication in the online phase, outperforming all prior state-of-the-art schemes while relying on lightweight cryptographic primitives. Lastly, we implement the solution from scratch in Python using efficient C++ blocks, testifying its high performance.
Last updated:  2022-12-04
Stronger Security and Generic Constructions for Adaptor Signatures
Wei Dai, Tatsuaki Okamoto, and Go Yamamoto
Last updated:  2022-12-04
Practical Quantum-Safe Voting from Lattices, Extended
Ian Black, Emma McFall, Juliet Whidden, Bryant Xie, and Ryann Cartor
E-voting offers significant potential savings in time and money compared to current voting systems. Unfortunately, many current e-voting schemes are susceptible to quantum attacks. In this paper, we expand upon EVOLVE, an existing lattice-based quantum-secure election scheme introduced by Pino et al. We are able to make these expansions by extending the dimensions of the voter's ballot and creating additional proofs, allowing for applicability to realistic election schemes. Thus, we present our system of schemes, called EVOLVED (Electronic Voting from Lattices with Verification and Extended Dimensions). We present schemes for numerous different types of elections including Single-Choice Voting, Borda Count, and Instant Runoff.
Last updated:  2022-12-04
CoRA: Collaborative Risk-Aware Authentication
Mastooreh Salajegheh, Shashank Agrawal, Maliheh Shirvanian, Mihai Christodorescu,, and Payman Mohassel
Today, authentication faces the trade-off of security versus usability. Two factor authentication, for example, is one way to improve security at the cost of requiring user interaction for every round of authentication. Most 2FA methods are bound to user's phone and fail if the phone is not available. We propose CoRA, a Collaborative Risk-aware Authentication method that takes advantage of any and many devices that the user owns. CoRA increases security, and preserves usability and privacy by using threshold MACs and by tapping into the knowledge of the devices instead of requiring user knowledge or interaction. Using CoRA, authentication tokens are generated collaboratively by multiple devices owned by the user, and the token is accompanied by a risk factor that indicates the reliability of the token to the authentication server. CoRA relies on a device-centric trust assessment to determine the relative risk factor and on threshold cryptography to ensure no single point of failure. CoRA does not assume any secure element or physical security for the devices. In this paper, we present the architecture and security analysis of CoRA. In an associated user study we discover that 78% of users have at least three devices with them at most times, and 93% have at least two, suggesting that deploying CoRA multi-factor authentication is practical today.
Last updated:  2022-12-04
Division in the Plactic Monoid
Chris Monico
In [1], a novel cryptographic key exchange technique was proposed using the plactic monoid, based on the apparent difficulty of solving division problems in that monoid. Specifically, given elements c, b in the plactic monoid, the problem is to find q for which qb = c, given that such a q exists. In this paper, we introduce a metric on the plactic monoid and use it to give a probabilistic algorithm for solving that problem which is fast for parameter values in the range of interest.
Last updated:  2022-12-03
Powers of Tau in Asynchrony
Sourav Das, Zhuolun Xiang, and Ling Ren
The $q$-Strong Diffie-Hellman ($q$-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive argument of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon. The only existing method to generate these parameters securely is highly sequential, requires strong network synchrony assumptions, and has very high communication and computation cost. For example, to generate parameters for any given $q$, each party incurs a communication cost of $\Omega(nq)$ and requires $\Omega(n)$ rounds. Here $n$ is the number of parties in the secure multiparty computation protocol. Since $q$ is typically large, i.e., on the order of billions, the cost is highly prohibitive. In this paper, we present Tauron, a distributed protocol to generate $q$-SDH parameters in an asynchronous network. In a network of $n$ parties, Tauron tolerates up to one-third of malicious parties. Each party incurs a communication cost of $O(q + n^2\log q)$ and the protocol finishes in $O(\log q + \log n)$ expected rounds. We provide a rigorous security analysis of our protocol. We implement Tauron and evaluate it with up to 128 geographically distributed parties. Our evaluation illustrates that Tauron is highly scalable and results in a 2-6$\times$ better runtime and 4-13$\times$ better per-party bandwidth usage.
Last updated:  2022-12-03
Interactive Authentication
Deepak Maram, Mahimna Kelkar, and Ittay Eyal
Authentication is the first, crucial step in securing digital assets like cryptocurrencies and online services like banking and social networks. It relies on principals maintaining exclusive access to credentials like cryptographic signing keys, passwords, and physical devices. But both individuals and organizations struggle to manage their credentials, resulting in loss of assets and identity theft. Multi-factor authentication improves security, but its analysis and design are mostly limited to one-shot mechanisms, which decide immediately. In this work, we study mechanisms with back-and-forth interaction with the principals. For example, a user receives an email notification about sending money from her bank account and is given a period of time to abort the operation. We formally define the authentication problem, where an authentication mechanism interacts with a user and an attacker and tries to identify the user. A mechanism's success depends on the scenario~-- whether the user / attacker know the different credentials; each credential can be safe, lost, leaked, or stolen. The profile of a mechanism is the set of all scenarios in which it succeeds. Thus, we have a partial order on mechanisms, defined by the subset relation on their profiles. We find an upper bound on the profile size and discover three types of $n$-credential mechanisms (for any $n$) that are maximally secure, meeting this bound. We show these are all the unique maximal mechanisms for $n \le 3$. We show the efficacy of our model by analyzing existing mechanisms, both theoretical and deployed in widely-used systems, and make concrete improvement proposals. We demonstrate the practicality of our mechanisms by implementing a maximally-secure cryptocurrency wallet.
Last updated:  2022-12-03
Backdooring Post-Quantum Cryptography: Kleptographic Attacks on Lattice-based KEMs
Prasanna Ravi, Shivam Bhasin, Anupam Chattopadhyay, Aikata, and Sujoy Sinha Roy
Post-quantum Cryptography (PQC) has reached the verge of standardization competition, with Kyber as a winning candidate. In this work, we demonstrate practical backdoor insertion in Kyber through kleptrography. The backdoor can be inserted using classical techniques like ECDH or post-quantum Classic Mceliece. The inserted backdoor targets the key generation procedure where generated output public keys subliminally leak information about the secret key to the owner of the backdoor. We demonstrate first practical instantiations of such attack at the protocol level by validating it on TLS 1.3.
Last updated:  2022-12-02
Authenticated Encryption with Key Identification
Julia Len, Paul Grubbs, and Thomas Ristenpart
Authenticated encryption with associated data (AEAD) forms the core of much of symmetric cryptography, yet the standard techniques for modeling AEAD assume recipients have no ambiguity about what secret key to use for decryption. This is divorced from what occurs in practice, such as in key management services, where a message recipient can store numerous keys and must identify the correct key before decrypting. To date there has been no formal investigation of their security properties or efficacy, and the ad hoc solutions for identifying the intended key deployed in practice can be inefficient and, in some cases, vulnerable to practical attacks. We provide the first formalization of nonce-based AEAD that supports key identification (AEAD-KI). Decryption now takes in a vector of secret keys and a ciphertext and must both identify the correct secret key and decrypt the ciphertext. We provide new formal security definitions, including new key robustness definitions and indistinguishability security notions. Finally, we show several different approaches for AEAD-KI and prove their security.
Last updated:  2022-12-02
Integer Polynomial Recovery from Outputs and its Application to Cryptanalysis of a Protocol for Secure Sorting
Srinivas Vivek, Shyam Murthy, and Deepak Kumaraswamy
{We investigate the problem of recovering integer inputs (up to an affine scaling) when given only the integer monotonic polynomial outputs. Given $n$ integer outputs of a degree-$d$ integer monotonic polynomial whose coefficients and inputs are integers within known bounds and $n \gg d$, we give an algorithm to recover the polynomial and the integer inputs (up to an affine scaling). A heuristic expected time complexity analysis of our method shows that it is exponential in the size of the degree of the polynomial but polynomial in the size of the polynomial coefficients. We conduct experiments with real-world data as well as randomly chosen parameters and demonstrate the effectiveness of our algorithm over a wide range of parameters. Using only the polynomial evaluations at specific integer points, the apparent hardness of recovering the input data served as the basis of security of a recent protocol proposed by Kesarwani et al. for secure $k$-nearest neighbour computation on encrypted data that involved secure sorting. The protocol uses the outputs of randomly chosen monotonic integer polynomial to hide its inputs except to only reveal the ordering of input data. Using our integer polynomial recovery algorithm, we show that we can recover the polynomial and the inputs within a few seconds, thereby demonstrating an attack on the protocol of Kesarwani et al.
Last updated:  2022-12-02
Practical Asynchronous Distributed Key Generation: Improved Efficiency, Weaker Assumption, and Standard Model
Haibin Zhang, Sisi Duan, Chao Liu, Boxin Zhao, Xuanji Meng, Shengli Liu, Yong Yu, Fangguo Zhang, and Liehuang Zhu
Last updated:  2022-12-01
Quagmire ciphers and group theory: What is a Porta cipher?
Thomas Kaeding
Uncategorized
It is an involutory (self-reciprocal) quagmire 4 cipher. Furthermore, it is isomorphic to a Beaufort. Explicit keys and transformations are provided.
Last updated:  2022-12-01
(Concurrently Secure) Blind Schnorr from Schnorr
Georg Fuchsbauer and Mathias Wolf
Many applications of blind signatures, such as those for blockchains, require the resulting signatures to be compatible with the existing system. This makes schemes that produce Schnorr signatures, which are now supported by major cryptocurrencies, including Bitcoin, desirable. Unfortunately, the existing blind-signing protocol has been shown insecure when users can open signing sessions concurrently (Eurocrypt'21). On the other hand, only allowing sequential sessions opens the door to denial-of-service attacks. We present the first concurrently secure blind-signing protocol for Schnorr signatures, using the standard primitives NIZK and PKE and assuming that Schnorr signatures themselves are unforgeable. We cast our scheme as a generalization of blind and partially blind signatures. We formally define the notion of predicate blind signatures, in which the signer can define a predicate that the blindly signed message must satisfy.
Last updated:  2022-12-01
SoK: Getting started with open-source fault simulation tools
Fault injection attacks have caused implementations to behave unexpectedly, leading to the extraction of cryptographic keys and the spectacular bypass of security features. Understandably, developers want to ensure the robustness of the software against faults and eliminate during production weaknesses that could lead to exploitation. Several open-source fault simulation tools have recently been released to the public, promising cost-effective fault evaluations. In this paper, we set out to discover how suitable such tools are for a developer who wishes to create robust software. The four fault simulation tools available to us employ different techniques to navigate faults and present varying difficulty levels to the user. We objectively compare the available open-source tools and discuss their benefits and drawbacks.
Last updated:  2022-12-01
Practical Multi-Key Homomorphic Encryption for More Flexible and Efficient Secure Federated Aggregation (preliminary work)
Alberto Pedrouzo-Ulloa, Aymen Boudguiga, Olive Chakraborty, Renaud Sirdey, Oana Stan, and Martin Zuber
In this work, we introduce a lightweight communication-efficient multi-key approach suitable for the Federated Averaging rule. By combining secret-key RLWE-based HE, additive secret sharing and PRFs, we reduce approximately by a half the communication cost per party when compared to the usual public-key instantiations, while keeping practical homomorphic aggregation performances. Additionally, for LWE-based instantiations, our approach reduces the communication cost per party from quadratic to linear in terms of the lattice dimension.
Last updated:  2022-12-01
DeV-IP: A k-out-n Decentralized and verifiable BFV for Inner Product evaluation
Jose Contreras and Hardik Gajera
The biometric system has become the desired alternative to a knowledge-based authentication system. An authentication system does not provide uniqueness, as a single user can create multiple registrations with different identities for authentication. Biometric authentication identifies users based on physical traits (fingerprint, iris, face, voice), which allows the system to detect multiple authentications from the same user. The biometric templates must be encrypted or hidden to preserve users' privacy. Moreover, we need a system to perform the matching process over encrypted data without decrypting templates to preserve the users' privacy. For the euclidean distance-based matching process, centralized server-based authentication leads to possible privacy violations of biometric templates since the power of computing inner product value over any two encrypted templates allows the server to retrieve the plain biometric template by computing a few inner products. To prevent this, we considered a decentralized system called collective authority, which is a part of a public network. The collective authority computes the collective public key with contributions from all nodes in the collective authority. It also performs a matching process over encrypted biometric templates in a decentralized manner where each node performs partial matching. Then the leader of the collective authority combines it to get the final value. We further provide a lattice-based verification system for each operation. Every time a node performs some computations, it needs to provide proof of the correctness of the computation, which is publicly verifiable. We finally make the system dynamics using Shamir's secret sharing scheme. In dynamic collective authority, only $k$ nodes out of the total $n$ nodes are required to perform the matching process. We further show that the security of the proposed system relies on the security of the underlying encryption scheme and the secret sharing scheme.
Last updated:  2022-12-01
An Auditable Confidentiality Protocol for Blockchain Transactions
Aoxuan Li, Gabriele D’Angelo, Jacky Tang, Frank Fang, and Baron Gong
Blockchain exposes all users’ transaction data to the public, including account balances, asset holdings, trading history, etc. Such data exposure leads to potential security and personal privacy risks that restrict blockchain from broader adoption. Although some existing projects focus on single-chain confidential payment, no existing cross-chain system supports private transactions yet, which is incompatible with privacy regulations such as GDPR. Also, current confidential payment systems require users to pay high extra fees. However, a private and anonymous protocol encrypting all transaction data raises concerns about malicious and illegal activities since the protocol is difficult to audit. We need to balance privacy and auditability in blockchain. We propose an auditable and affordable protocol for cross-chain and single-chain transactions. This protocol leverages zero-knowledge proofs to encrypt transactions and perform validation without disclosing sensitive users' data. To meet regulations, each auditor from an auditing committee will have an encrypted secret share of the transaction data. Auditors may view the private transaction data only if a majority of the committee agrees to decrypt the data. We employ a ZK-rollup scheme by processing multiple transactions in batches, which reduces private transaction costs to 90\% lower compared with solutions without ZK-rollup. We implemented the proposed scheme using Zokrates and Solidity and evaluated the protocol on the Ethereum test network, and the total one-to-one private transactions cost only 5 seconds. We also proved the security of the protocol utilizing the standard real/ideal world paradigm.
Last updated:  2022-12-01
Quantum Neural Network based Distinguisher for Differential Cryptanalysis on Simplified Block Ciphers
Hyunji Kim, Kyungbae Jang, Sejin Lim, Yeajun Kang, Wonwoong Kim, and Hwajeong Seo
Differential cryptanalysis is a block cipher analysis technology that infers a key by using the difference characteristics. Input differences can be distinguished using a good difference characteristic, and this distinguishing task can lead to key recovery. Artificial neural networks are a good solution for distinguishing tasks. For this reason, recently, neural distinguishers have been actively studied. We propose a distinguisher based on a quantum-classical hybrid neural network by utilizing the recently developed quantum neural network. To our knowledge, we are the first attempt to apply quantum neural networks for neural distinguisher. The target ciphers are simplified ciphers (S-DES, S-AES, S-PRESENT-[4]), and a quantum neural distinguisher that classifies the input difference from random data was constructed using the Pennylane library. Finally, we obtained quantum advantages in this work: improved accuracy and reduced number of parameters. Therefore, our work can be used as a quantum neural distinguisher with high reliability for simplified ciphers.
Last updated:  2022-12-01
Compactly Committing Authenticated Encryption Using Encryptment and Tweakable Block Cipher
Shoichi Hirose and Kazuhiko Minematsu
Facebook introduced message franking to enable users to report abusive content verifiably in end-to-end encrypted messaging. Grubbs et al. formalized the underlying primitive called compactly committing authenticated encryption with associated data (ccAEAD) and presented schemes with provable security. Dodis et al. proposed a core building block called encryptment and presented a generic construction of ccAEAD with encryptment and standard AEAD. This paper first proposes to use a tweakable block cipher instead of AEAD for the generic construction of Dodis et al. In the security analysis of the proposed construction, its ciphertext integrity is shown to require a new but feasible assumption on the ciphertext integrity of encryptment. Then, this paper formalizes remotely keyed ccAEAD (RK ccAEAD) and shows that the proposed construction works as RK ccAEAD. Finally, the confidentiality of the proposed construction as RK ccAEAD is shown to require a new variant of confidentiality for encryptment. The problem of remotely keyed encryption was posed by Blaze in 1996. It is now related to the problem of designing a cryptographic scheme using a trusted module and/or with leakage resiliency.
Last updated:  2022-11-30
Jolt: Recovering TLS Signing Keys via Rowhammer Faults
Koksal Mus, Yarkın Doröz, M. Caner Tol, Kristi Rahman, and Berk Sunar
Digital Signature Schemes such as DSA, ECDSA, and RSA are widely deployed to protect the integrity of security protocols such as TLS, SSH, and IPSec. In TLS, for instance, RSA and (EC)DSA are used to sign the state of the agreed upon protocol parameters during the handshake phase. Naturally, RSA and (EC)DSA implementations have become the target of numerous attacks, including powerful side-channel attacks. Hence, cryptographic libraries were patched repeatedly over the years. Here we introduce Jolt, a novel attack targeting signature scheme implementations. Our attack exploits faulty signatures gained by injecting faults during signature generation. By using the signature verification primitive, we correct faulty signatures and, in the process deduce bits of the secret signing key. Compared to recent attacks that exploit single bit biases in the nonce that require $2^{45}$ signatures, our attack requires less than a thousand faulty signatures for a $256$-bit (EC)DSA. The performance improvement is due to the fact that our attack targets the secret signing key, which does not change across signing sessions. We show that the proposed attack also works on Schnorr and RSA signatures with minor modifications. We demonstrate the viability of Jolt by running experiments targeting TLS handshakes in common cryptographic libraries such as WolfSSL, OpenSSL, Microsoft SymCrypt, LibreSSL, and Amazon s2n. On our target platform, the online phase takes less than 2 hours to recover $192$ bits of a $256$-bit ECDSA key, which is sufficient for full key recovery. We note that while RSA signatures are protected in popular cryptographic libraries, OpenSSL remains vulnerable to double fault injection. We have also reviewed their FIPS hardened versions which is slightly less efficient but still vulnerable to our attack. We found that (EC)DSA signatures remain largely unprotected against software-only faults, posing a threat to real-life deployments such as TLS, and potentially other security protocols such as SSH and IPSec. This highlights the need for a thorough review and implementation of faults checking in security protocol implementations.
Last updated:  2022-11-30
On the families of graphs with the fastest growth of girth and their usage in cryptography
Vasyl Ustimenko
Symbolic computations with usage of algebraic graphs A(n; F_q) and A(n;,F_q[x_1, x_2,..., x_n]) were used for the development of various cryptographic algorithms because the length of their minimal cycle (the girth) tends to infinity when n is growing. It was announced recently that for each commutative integrity ring the girth of A(n, K) is ≥ 2n. In this paper we present essentially shorter closed proof of this statement and evaluate the girth of some induced subgraphs of A(n; K[x_1, x_2, ..., x_n]).
Last updated:  2022-11-30
Applying Castryck-Decru Attack on the Masked Torsion Point Images SIDH variant
Jesús-Javier Chi-Domínguez
This paper illustrates that masking the torsion point images does not guarantee Castryck-Decru attack does not apply. Our experiments over SIDH primes hint that any square root concerning the Weil pairing on the masked public key helps to recover Bob's private key via the Castryck-Decru attack.
Last updated:  2022-11-30
Cryptanalysis of Ivanov-Krouk-Zyablov cryptosystem
Kirill Vedenev and Yury Kosolapov
Recently, F.Ivanov, E.Krouk and V.Zyablov proposed new cryptosystem based of Generalized Reed--Solomon (GRS) codes over field extensions. In their approach, the subfield images of GRS codes are masked by a special transform, so that the resulting public codes are not equivalent to subfield images of GRS code but burst errors still can be decoded. In this paper, we show that the complexity of message-recovery attack on this cryptosystem can be reduced due to using burst errors, and the secret key of Ivanov-Krouk-Zyablov cryptosystem can successfully recovered in polynomial time with a linear-algebra based attack and a square-based attack.
Last updated:  2022-11-30
GCKSign: Simple and Efficient Signatures from Generalized Compact Knapsacks
Joo Woo, Kwangsu Lee, and Jong Hwan Park
In 2009, Lyubashevsky proposed a lattice-based signature scheme by applying the Fiat-Shamir transformation and proved its security under the generalized compact knapsack (GCK) problem. This scheme has a simple structure but has large signature and key sizes due to the security requirement of their security reduction. Dilithium, which was submitted to the NIST Post-Quantum Cryptography standardization and selected as one of the final candidates, is an improvement of the Lyubashevsky's signature scheme and decreases key and signature sizes by modifying the form of a public key and including additional steps in key generation, signing, and verification algorithms. Thus, Dilithium has a more complex structure to implement compared to the Lyubashevsky's scheme. To combine the strength of both signature schemes, we modify the Lyubashevsky's signature scheme and present a new security proof that removes their security requirement. As a result, we propose a simple and practical GCKSign signature scheme based on the hardness of a new GCK assumption, called target-modified one-wayness of GCK function. The signature size of our signature scheme decreases 40 percent, the sum of signature and public key sizes decreases 25 percent, and the secret key size decreases 90 percent for the NIST security level III, compared to Dilithium. Furthermore, by the simplicity of our structure, the key generation, signing, and verification algorithms of our scheme run 2.4$\times$, 1.7$\times$, and 2.0$\times$ faster than those of Dilithium, respectively.
Last updated:  2022-11-30
NTRU+: Compact Construction of NTRU Using Simple Encoding Method
Jonghyun Kim and Jong Hwan Park
NTRU was the first practical public-key encryption scheme constructed on a lattice over a polynomial-based ring, and has been still considered secure against significant cryptanalytic attacks in a few decades. Despite such a long history, NTRU and its variants proposed to date suffer from several drawbacks, such as the difficulty of achieving worst-case correctness error in a moderate modulus, inconvenient sampling distributions for messages, and relatively slower algorithms than other lattice-based schemes. In this work, we suggest a new NTRU-based key encapsulation mechanism (KEM), called NTRU+, which overcomes almost all existing drawbacks. NTRU+ is constructed based on two new generic transformations called $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$. $\mathsf{ACWC}_{2}$ is used for easily achieving a worst-case correctness error, and $\overline{\mathsf{FO}}^{\perp}$ (as a variant of the Fujisaki-Okamoto transform) is used for achieving chosen-ciphertext security without re-encryption. $\mathsf{ACWC}_{2}$ and $\overline{\mathsf{FO}}^{\perp}$ are all defined using a randomness-recovery algorithm and an encoding method. Especially, our simple encoding method, called $\mathsf{SOTP}$, allows us to sample a message from a natural bit-sting space with an arbitrary distribution. We provide four parameter sets for NTRU+ and give implementation results, using NTT-friendly rings over cyclotomic trinomials.
Last updated:  2022-11-29
REDOG and Its Performance Analysis
Jon-Lark Kim, Jihoon Hong, Terry Shue Chien Lau, YounJae Lim, Chik How Tan, Theo Fanuela Prabowo, and Byung-Sun Won
We propose a REinforced modified Dual-Ouroboros based on Gabidulin codes, shortly called REDOG. This is a code-based cryptosystem based on the well-known rank metric codes, Gabidulin codes. The public key sizes of REDOG are 14KB, 33KB, 63KB at the security levels of 128, 192, 256 bits respectively. There is no decoding failure in decryption. REDOG is IND-CPA. As a new result, we give the performance results of implementing REDOG including the time for Key generation, encryption, and decryption for each security level.
Last updated:  2022-11-29
Revisiting cycles of pairing-friendly elliptic curves
Marta Bellés-Muñoz, Jorge Jiménez Urroz, and Javier Silva
A recent area of interest in cryptography is recursive composition of proof systems. One of the approaches to make recursive composition efficient involves cycles of pairing-friendly elliptic curves of prime order. However, known constructions have very low embedding degrees. This entails large parameter sizes, which makes the overall system inefficient. In this paper, we explore $2$-cycles composed of curves from families parameterized by polynomials, and show that such cycles do not exist unless a strong condition holds. As a consequence, we prove that no $2$-cycles can arise from the known families, except for those cycles already known. Additionally, we show some general properties about cycles, and provide a detailed computation on the density of pairing-friendly cycles among all cycles.
Last updated:  2022-12-01
Enhancing the Dual Attack against MLWE: Constructing More Short Vectors Using Its Algebraic Structure
Han Wu and Guangwu Xu
Primal attack, BKW attack, and dual attack are three well-known attacks to LWE. To build efficient post-quantum cryptosystems in practice, the structured variants of LWE (i.e. MLWE/RLWE) are often used. Some efforts have been spent on addressing concerns about additional vulnerabilities introduced by algebraic structures and no effective attack method based on ideal lattices or module lattices has been proposed so far; these include refining primal attack and BKW attack to MLWE/RLWE. It is thus an interesting problem to consider how to enhance the dual attack against LWE with the rich algebraic structure of MLWE (including RLWE). In this paper, we present the first attempt to this problem by observing that each short vector found by BKZ generates another n − 1 vectors of the same length automatically and all of these short vectors can be used to distinguish. To this end, an interesting property which indicates the rotations are consistent with certain linear transformations is proved, and a new kind of intersection lattice is constructed with some tricks. Moreover, we notice that coefficient vectors of different rotations of the same polynomial are near-orthogonal in high-dimensional spaces. This is validated by extensive experiments and is treated as an extension to the assumption under the original dual attack against LWE. Taking Newhope512 as an example, we show that by our enhanced dual attack method, the required blocksize and time complexity (in both classical and quantum cases) all decrease. It is remarked that our improvement is not significant and its limitation is also touched on. Our results do not reveal a severe security problem for MLWE/RLWE compared to that of a general LWE, this is consistent with the findings by the previous work for using primal and BKW attacks to MLWE/RLWE.
Last updated:  2022-11-29
Owner Identity Verification in the Internet of Connected Vehicles: Zero Trust Based Solution
Mashrukh Zayed, Adnan Anwar, Ziaur Rahman, Sk. Shezan Arefin, and Rafiqul Islam
On the Internet of Connected Vehicles, a vehicle has to communicate bi-directionally with several devices for establishing a shared network for inter-vehicle and intra-vehicle connectivity. These connection protocols are commonly structured to connect all the individual components with an implicit degree of trust, which is supposed to protect the whole system from unauthorized users. Technologies like Automotive Ethernet tend to increase security by reducing the implicit trust within the local network devices. However, the lack of individual security protocols in vehicle-to-vehicle communication still keeps the possession of vulnerability to hacks, external attacks, and further disruption. This is where Zero Trust Architecture can become a reliable technology for the exchange of information in between vehicles. Zero trust is a security system that means no one is trusted by default and verification is required from anyone or any device willing to get connected to the intra-vehicle network. In this paper, we have scoped the preliminary and most vital step of this system: verifying the owner identity of a vehicle with zero trust manner. Our approach involves recognizing vehicle license plates and utilizing the license information for retrieving the vehicle owner details to establish trust before allowing connection to the network. Our proposed methodology operates with 85\% to 99\% accuracy on the license recognition part within recognizable distances using PyTesseract OCR. Reliability to the zero trust solution is gained through necessary information retrieved using GET and POST requests to and from the corresponding driving license information databases.
Last updated:  2022-11-29
A Deep Learning aided Key Recovery Framework for Large-State Block Ciphers
Yi Chen, Zhenzhen Bao, Yantian Shen, and Hongbo Yu
In the seminal work published by Gohr in CRYPTO 2019, neural networks were successfully exploited to perform differential attacks on Speck32/64, the smallest member in the block cipher family Speck. The deep learning aided key-recovery attack by Gohr achieves considerable improvement in terms of time complexity upon the state-of-the-art result from the conventional cryptanalysis method. A further question is whether the advantage of deep learning aided attacks can be kept on large-state members of Speck and other primitives. Since there are several key points in Gohr’s key-recovery frameworks that seem not fit for large-state ciphers, this question stays open for years. This work provides an answer to this question by proposing a deep learning aided multi-stage key-recovery framework. To apply this key-recovery framework on large-state members of Speck, multiple neural distinguishers (NDs) are trained and carefully combined into groups. Employing the groups of NDs under the multi-stage key-recovery framework, practical attacks are designed and trialed. Experimental results show the effectiveness of the framework. The practical attacks are then extended into theoretical attacks that cover more rounds. To do that, multi-round classical differentials (CDs) are used together with the NDs. To find the CDs’ neutral bits to boost signals from the distinguishers, an efficient algorithm is proposed. As a result, considerable improvement in terms of both time and data complexity of differential key-recovery attacks on round-reduced Speck with the largest, i.e., the 128-bit state, is obtained. Besides, efficient differential attacks are achieved on round-reduced Speck with 96-bit and 64-bit states. Since most real-world block ciphers have a state size of no less than 64 bits, this work paves the way for performing cryptanalysis using deep learning on more block ciphers. The code is available at https://github.com/AI-Lab-Y/NAAF.
Last updated:  2022-11-28
A new Privacy Preserving and Scalable Revocation Method for Self Sovereign Identity - The Perfect Revocation Method does not exist yet
Andreas Freitag
Digital Identities are playing an essential role in our digital lives. Today, most Digital Identities are based on central architectures. Central Digital Identity providers control and know our data and thereby our Identity. Self Sovereign Identities are based on decentralized data storage and data exchange architecture, where the user is in sole control of his data and identity. Most of the issued credentials need the possibility of revocation. For a centrally managed Digital Identity system, revocation is not a problem. In decentral architectures, revocation is more challenging. Revocation can be done with different methods e.g. list based, cryptographic accumulators and with credential updates. A revocation method must be privacy preserving and must scale. This paper gives an overview of the available revocation methods, including a survey to define requirements, assess revocation groups against the requirements, highlights shortcomings of the methods and introduces a new revocation method called Linked Validity Verifiable Credentials.
Last updated:  2022-11-28
CycloneNTT: An NTT/FFT Architecture Using Quasi-Streaming of Large Datasets on DDR- and HBM-based FPGA Platforms
Kaveh Aasaraai, Emanuele Cesena, Rahul Maganti, Nicolas Stalder, Javier Varela, and Kevin Bowers
Number-Theoretic-Transform (NTT) is a variation of Fast-Fourier-Transform (FFT) on finite fields. NTT is being increasingly used in blockchain and zero-knowledge proof applications. Although FFT and NTT are widely studied for FPGA implementation, we believe CycloneNTT is the first to solve this problem for large data sets ($\ge2^{24}$, 64-bit numbers) that would not fit in the on-chip RAM. CycloneNTT uses a state-of-the-art butterfly network and maps the dataflow to hybrid FIFOs composed of on-chip SRAM and external memory. This manifests into a quasi-streaming data access pattern minimizing external memory access latency and maximizing throughput. We implement two variants of CycloneNTT optimized for DDR and HBM external memories. Although historically this problem has been shown to be memory-bound, CycloneNTT's quasi-streaming access pattern is optimized to the point that when using HBM (Xilinx C1100), the architecture becomes compute-bound. On the DDR-based platform (AWS F1), the latency of the application is equal to the streaming of the entire dataset $\log N$ times to/from external memory. Moreover, exploiting HBM's larger number of channels, and following a series of additional optimizations, CycloneNTT only requires $\frac{1}{6}\log N$ passes.
Last updated:  2022-11-28
Accountable Threshold Signatures with Proactive Refresh
Dan Boneh, Aditi Partap, and Lior Rotem
An accountable threshold signature (ATS) is a threshold signature scheme where every signature identifies the quorum of signers who generated that signature. They are widely used in financial settings where signers need to be held accountable for threshold signatures they generate. In this paper we initiate the study of proactive refresh for accountable threshold signatures. Proactive refresh is a protocol that lets the group of signers refresh their shares of the secret key, without changing the public key or the threshold. We give several definitions for this notion achieving different levels of security. We observe that certain natural constructions for an ATS cannot be proactively refreshed because the secret key generated at setup is needed for accountability. We then construct three types of ATS schemes with proactive refresh. The first is a generic construction that is efficient when the number of signers is small. The second is a hybrid construction that performs well for a large number of signers and satisfies a strong security definition. The third is a collection of very practical constructions derived from ATS versions of the Schnorr and BLS signature schemes; however these practical constructions only satisfy our weaker notion of security.
Last updated:  2022-11-28
Just How Fair is an Unreactive World?
Srinivasan Raghuraman and Yibin Yang
Fitzi, Garay, Maurer, and Ostrovsky (J. Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we show that in the presence of $n - 1$ corrupt parties, no unreactive primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with fairness. We show more generally that for $t > \frac{n}{2}$, in the presence of $t$ malicious parties, no unreactive primitive of cardinality $t$ is complete for realizing an arbitrary $n$-party functionality with fairness. We complement this result by noting that $(t+1)$-wise fair exchange is complete for realizing an arbitrary $n$-party functionality with fairness. In order to prove our results, we utilize the primitive of fair coin tossing and introduce the notion of predictability in coin tossing protocols, which we believe is of independent interest.
Last updated:  2022-11-29
On the Complete Non-Malleability of the Fujisaki-Okamoto Transform
Daniele Friolo, Matteo Salvino, and Daniele Venturi
The Fujisaki-Okamoto (FO) transform (CRYPTO 1999 and JoC 2013) turns any weakly (i.e., IND-CPA) secure public-key encryption (PKE) scheme into a strongly (i.e., IND-CCA) secure key encapsulation method (KEM) in the random oracle model (ROM). Recently, the FO transform re-gained momentum as part of CRISTAL-Kyber, selected by the NIST as the PKE winner of the post-quantum cryptography standardization project. Following Fischlin (ICALP 2005), we study the complete non-malleability of KEMs obtained via the FO transform. Intuitively, a KEM is completely non-malleable if no adversary can maul a given public key and ciphertext into a new public key and ciphertext encapsulating a related key for the underlying blockcipher. On the negative side, we find that KEMs derived via FO are not completely non-malleable in general. On the positive side, we show that complete non-malleability holds in the ROM by assuming the underlying PKE scheme meets an additional property, or by a slight tweak of the transformation.
Last updated:  2022-11-28
Reversing, Breaking, and Fixing the French Legislative Election E-Voting Protocol
Alexandre Debant and Lucca Hirschi
We conduct a security analysis of the e-voting protocol used for the largest political election using e-voting in the world, the 2022 French legislative election for the citizens overseas. Due to a lack of system and threat model specifications, we built and contributed such specifications by studying the French legal framework and by reverse-engineering the code base accessible to the voters. Our analysis reveals that this protocol is affected by two design-level and implementation-level vulnerabilities. We show how those allow a standard voting server attacker and even more so a channel attacker to defeat the election integrity and ballot privacy due to 6 attack variants. We propose and discuss 5 fixes to prevent those attacks. Our specifications, the attacks, and the fixes were acknowledged by the relevant stakeholders during our responsible disclosure. Our attacks are in the process of being prevented with our fixes for future elections. Beyond this specific protocol, we draw general conclusions and lessons from this instructive experience where an e-voting protocol meets the real-world constraints of a large-scale and political election.
Last updated:  2022-11-28
Improved Universal Circuits using Lookup Tables
Yann Disser, Daniel Günther, Thomas Schneider, Maximilian Stillger, Arthur Wigandt,, and Hossein Yalame
A Universal Circuit (UC) is a Boolean circuit of size $\Theta(n \log n)$ that can simulate any Boolean function up to a certain size $n$. Valiant (STOC'76) provided the first two UC constructions of asymptotic sizes $\sim5 n\log n$ and $\sim4.75 n\log n$, and today's most efficient construction of Liu et al. (CRYPTO'21) has size $\sim3n\log n$. Evaluating a public UC with a secure Multi-Party Computation (MPC) protocol allows efficient Private Function Evaluation (PFE), where a private function is evaluated on private data. Most existing UC constructions simulate circuits consisting of 2-input gates. In this work, we study UCs that simulate circuits consisting of ($\rho \rightarrow \omega$)-Lookup Tables (LUTs) that map $\rho$ inputs to $\omega$ outputs. Existing UC constructions can be easily extend to ($\rho \rightarrow$ 1)-LUTs (we call this the fixed UC construction). We further extend this to ($\rho \rightarrow \omega$)-LUTs. Unfortunately, the size of the fixed UC construction is linear in the largest input size $\rho$ of the LUT, i.e., even if only a single LUT in the circuit has a large input size, the size of the whole UC is dominated by this LUT size. To circumvent this, we design a \emph{dynamic} UC construction, where the dimensions of the individual LUTs are public. We implement the fixed and dynamic UC constructions based on the UC construction by Liu et al., which also is the first implementation of their construction. We show that the concrete size of our dynamic UC construction improves by at least $2\times$ over Liu et al.'s UC for all benchmark circuits, that are representative for many PFE applications.
Last updated:  2022-11-28
TiGER: Tiny bandwidth key encapsulation mechanism for easy miGration based on RLWE(R)
Seunghwan Park, Chi-Gon Jung, Aesun Park, Joongeun Choi, and Honggoo Kang
The quantum resistance Key Encapsulation Mechanism (PQC-KEM) design aims to replace cryptography in legacy security protocols. It would be nice if PQC-KEM were faster and lighter than ECDH or DH for easy migration to legacy security protocols. However, it seems impossible due to the temperament of the secure underlying problems in a quantum environment. Therefore, it makes reason to determine the threshold of the scheme by analyzing the maximum bandwidth the legacy security protocol can adapt. We specified the bandwidth threshold at 1,244 bytes based on IKEv2 (RFC7296), a security protocol with strict constraints on payload size in the initial exchange for secret key sharing. We propose TiGER that is an IND-CCA secure KEM based on RLWE(R). TiGER has a ciphertext (1,152bytes) and a public key (928 bytes) smaller than 1,244 bytes, even at the AES256 security level. To our knowledge, TiGER is the only scheme with such an achievement. Also, TiGER satisfies security levels 1, 3, and 5 of NIST competition. Based on reference implementation, TiGER is 1.7-2.6x faster than Kyber and 2.2-4.4x faster than LAC.
Last updated:  2022-11-28
LightSwap: An Atomic Swap Does Not Require Timeouts At Both Blockchains
Philipp Hoenisch, Subhra Mazumdar, Pedro Moreno-Sanchez, and Sushmita Ruj
Security and privacy issues with centralized exchange services have motivated the design of atomic swap protocols for decentralized trading across currencies. These protocols follow a standard blueprint similar to the 2-phase commit in databases: (i) both users first lock their coins under a certain (cryptographic) condition and a timeout; (ii-a) the coins are swapped if the condition is fulfilled; or (ii-b) coins are released after the timeout. The quest for these protocols is to minimize the requirements from the scripting language supported by the swapped coins, thereby supporting a larger range of cryptocurrencies. The recently proposed universal atomic swap protocol [IEEE S&P’22] demonstrates how to swap coins whose scripting language only supports the verification of a digital signature on a transaction. However, the timeout functionality is cryptographically simulated with verifiable timelock puzzles, a computationally expensive primitive that hinders its use in battery-constrained devices such as mobile phones. In this state of affairs, we question whether the 2-phase commit paradigm is necessary for atomic swaps in the first place. In other words, is it possible to design a secure atomic swap protocol where the timeout is not used by (at least one of the two) users? In this work, we present LightSwap, the first secure atomic swap protocol that does not require the timeout functionality (not even in the form of a cryptographic puzzle) by one of the two users. LightSwap is thus better suited for scenarios where a user, running an instance of LightSwap on her mobile phone, wants to exchange coins with an online exchange service running an instance of LightSwap on a computer. We show how LightSwap can be used to swap Bitcoin and Monero, an interesting use case since Monero does not provide any scripting functionality support other than linkable ring signature verification.
Last updated:  2022-11-29
Robustness of Affine and Extended Affine Equivalent Surjective S-Box(es) against Differential Cryptanalysis
Shah Fahd, Mehreen Afzal, Dawood Shah, Waseem Iqbal, and Atiya Hai
A Feistel Network (FN) based block cipher relies on a Substitution Box (S-Box) for achieving the non-linearity. S-Box is carefully designed to achieve optimal cryptographic security bounds. The research of the last three decades shows that considerable efforts are being made on the mathematical design of an S-Box. To import the exact cryptographic profile of an S-Box, the designer focuses on the Affine Equivalent (AE) or Extended Affine (EA) equivalent S-Box. In this research, we argue that the Robustness of surjective mappings is invariant under AE and not invariant under EA transformation. It is proved that the EA equivalent of a surjective mapping does not necessarily contribute to the Robustness against the Differential Cryptanalysis (DC) in the light of Seberry's criteria. The generated EA equivalent S-Box(es) of DES and other $6 \times 4$ mappings do not show a good robustness profile compared to the original mappings. This article concludes that a careful selection of affine permutation parameters is significant during the design phase to achieve high Robustness against DC and Differential Power Analysis (DPA) attacks.
Last updated:  2022-11-28
Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs
Moumita Dutta, Chaya Ganesh, Sikhar Patranabis, and Nitin Singh
Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some trusted authority. We propose a generic and efficient compiler that transforms any linear secret sharing based MPC protocol into one with input authentication. Our compiler incurs significantly lower computational costs and competitive communication overheads when compared to the best existing solutions, while entirely avoiding the (potentially expensive) protocol-specific techniques and pre-processing requirements that are inherent to these solutions. For $n$-party MPC protocols with abort security where each party has $\ell$ inputs, our compiler incurs $O(n\log \ell)$ communication overall and a computational overhead of $O(\ell)$ group exponentiations per party (the corresponding overheads for the most efficient existing solution are $O(n^2)$ and $O(\ell n)$). Finally, for a corruption threshold $t<n/4$, our compiler preserves the stronger identifiable abort security of the underlying MPC protocol. No existing solution for authenticated MPC achieves this regardless of the corruption threshold. Along the way, we make several technical contributions that are of independent interest. This includes the notion of distributed proofs of knowledge and concrete realizations of the same for several relations of interest, such as proving knowledge of many popularly used digital signature schemes, and proving knowledge of opening of a Pedersen commitment. We also illustrate the practicality of our approach by extending the well-known MP-SPDZ library with our compiler, thus yielding prototype authenticated MPC protocols.
Last updated:  2022-11-28
Quantum Algorithm for Oracle Subset Product
Trey Li
In 1993 Bernstein and Vazirani proposed a quantum algorithm for the Bernstein-Vazirani problem, which is given oracle access to the function $f(a_1,\dots,a_n) = a_1x_1+\cdots + a_nx_n \pmod 2$ with respect to a secret string $x = x_1\dots x_n \in \{0,1\}^n$, where $a_1,\dots,a_n \in \{0,1\}$, find $x$. We give a quantum algorithm for a new problem called the oracle subset product problem, which is given oracle access to the function $f(a_1,\dots,a_n) = a_1^{x_1}\cdots a_n^{x_n}$ with respect to a secret string $x = x_1\dots x_n\in\{0,1\}^n$, where $a_1,\dots,a_n\in \mathbb Z$, find $x$. Similar to the Bernstein-Vazirani algorithm, it is a quantum algorithm for a problem that is originally polynomial time solvable by classical algorithms; and that the advantage of the algorithm over classical algorithms is that it only makes one call to the function instead of $n$ calls.
Last updated:  2022-11-27
Blockin: Multi-Chain Sign-In Standard with Micro-Authorizations
Matt Davison, Ken King, and Trevor Miller
The tech industry is currently making the transition from Web 2.0 to Web 3.0, and with this transition, authentication and authorization have been reimag- ined. Users can now sign in to websites with their unique public/private key pair rather than generating a username and password for every site. How- ever, many useful features, like role-based access control, dynamic resource owner privileges, and expiration tokens, currently don’t have efficient Web 3.0 solutions. Our solution aims to provide a flexible foundation for resource providers to implement the aforementioned features on any blockchain through a two-step process. The first step, authorization, creates an on-chain asset which is to be presented as an access token when interacting with a resource. The second step, authentication, verifies ownership of an asset through querying the blockchain and cryptographic digital signatures. Our solution also aims to be a multi-chain standard, whereas current Web 3.0 sign-in standards are limited to a single blockchain.
Last updated:  2022-11-25
The Return of the SDitH
Carlos Aguilar-Melchor, Nicolas Gama, James Howe, Andreas Hülsing, David Joseph, and Dongze Yue
This paper presents a code-based signature scheme based on the well-known syndrome decoding (SD) problem. The scheme builds upon a recent line of research which uses the Multi-Party-Computation-in-the-Head (MPCitH) approach to construct efficient zero-knowledge proofs, such as Syndrome Decoding in the Head (SDitH), and builds signature schemes from them using the Fiat-Shamir transform. At the heart of our proposal is a new approach to amplify the soundness of any MPC protocol that uses additive secret sharing. An MPCitH protocol with $N$ parties can be repeated $D$ times using parallel composition to reach the same soundness as a protocol run with $N^D$ parties. However, the former comes with $D$ times higher communication costs, often mainly contributed by the usage of $D$ auxiliary' states (which in general have a significantly bigger impact on size than random states). Instead of that, we begin by generating $N^D$ shares, arranged into a $D$-dimensional hypercube of side $N$ containing only one auxiliary' state. We derive from this hypercube $D$ sharings of size $N$ which are used to run $D$ instances of an $N$ party MPC protocol. This approach leads to an MPCitH protocol with $1/N^D$ soundness error, requiring $N^D$ offline computation, only $ND$ online computation, and only $1$ auxiliary'. As the, potentially offline, share generation phase is generally inexpensive, this leads to trade-offs that are superior to just using parallel composition. Our novel method of share generation and aggregation not only improves certain MPCitH protocols in general but also shows in concrete improvements of signature schemes. Specifically, we apply it to the work of Feneuil, Joux, and Rivain (CRYPTO'22) on code-based signatures, and obtain a new signature scheme that achieves a 3.3x improvement in global runtime, and a 15x improvement in online runtime for their shortest signatures size (8.5 kB). It is also possible to leverage the fact that most computations are offline to define parameter sets leading to smaller signatures: 6.7 kB for 60 ms offline, or 5.6 kB for 700 ms offline. For NIST security level 1, online signature cost is around 3 million cycles (1 ms on commodity processors), regardless of signature size.
Last updated:  2022-11-25
An attack on a key exchange protocol based on max-times and min-times algebras
Matvei Kotov, Alexander Treier, and Ivan Buchinskiy
In this paper, we examine one of the public key exchange protocols proposed in [M. I. Durcheva. An application of different dioids in public key cryptography. In AIP Conference Proceedings, vol. 1631, pp 336-343. AIP, 2014] which uses max-times and min-times algebras. We discuss properties of powers of matrices over these algebras and introduce a fast attack on this protocol.
Last updated:  2022-11-25
End-to-End Secure Messaging with Traceability Only for Illegal Content
James Bartusek, Sanjam Garg, Abhishek Jain, and Guru-Vamsi Policharla
As end-to-end encrypted messaging services become widely adopted, law enforcement agencies have increasingly expressed concern that such services interfere with their ability to maintain public safety. Indeed, there is a direct tension between preserving user privacy and enabling content moderation on these platforms. Recent research has begun to address this tension, proposing systems that purport to strike a balance between the privacy of ''honest'' users and traceability of ''malicious'' users. Unfortunately, these systems suffer from a lack of protection against malicious or coerced service providers. In this work, we address the privacy vs. content moderation question through the lens of pre-constrained cryptography [Ananth et al., ITCS 2022]. We introduce the notion of set pre-constrained (SPC) group signatures that guarantees security against malicious key generators. SPC group signatures offer the ability to trace users in messaging systems who originate pre-defined illegal content (such as child sexual abuse material), while providing security against malicious service providers. We construct concretely efficient protocols for SPC group signatures, and demonstrate the real-world feasibility of our approach via an implementation. The starting point for our solution is the recently introduced Apple PSI system, which we significantly modify to improve security and expand functionality.
Last updated:  2022-11-25
Proofs of Proof-of-Stake with Sublinear Complexity
Shresth Agrawal, Joachim Neu, Ertem Nusret Tas, and Dionysis Zindros
Popular Ethereum wallets (e.g., MetaMask) entrust centralized infrastructure providers (e.g., Infura) to run the consensus client logic on their behalf. As a result, these wallets are light-weight and high-performant, but come with security risks. A malicious provider can mislead the wallet, e.g., fake payments and balances, or censor transactions. On the other hand, light clients, which are not in popular use today, allow decentralization, but at concretely inefficient and asymptotically linear bootstrapping complexity. This poses a dilemma between decentralization and performance. In this paper, we design, implement, and evaluate concretely efficient and asymptotically logarithmic bootstrapping complexity. Our proofs of proof-of-stake (PoPoS) take the form of a Merkle tree of PoS epochs. The verifier enrolls the provers in a bisection game, in which the honest prover is destined to win once an adversarial Merkle tree is challenged at sufficient depth. To evaluate our superlight protocol, we provide a client implementation that is compatible with mainnet PoS Ethereum: compared to the state-of-the-art light client construction of PoS Ethereum, our client improves time-to-completion by 9x, communication by 180x, and energy usage by 30x (when bootstrapping after 10 years of consensus execution). We prove that our construction is secure and show how to employ it for other PoS systems such as Cardano (with full adaptivity), Algorand, and Snow White.
Last updated:  2022-11-25
AlgSAT --- a SAT Method for Search and Verification of Differential Characteristics from Algebraic Perspective
Huina Li, Guozhen Liu, Haochen Zhang, Kai Hu, Jian Guo, and Weidong Qiu
A good differential is a start for a successful differential attack. However, a differential might be invalid, i.e., there is no right pair following the differential1, due to some complicated contradictions that are hard to be considered. In this paper, we present a novel and handy method to search and verify a differential characteristic (DC) based on a recently proposed algebraic perspective on the differential(-linear) cryptanalysis (CRYPTO 2021). From this algebraic perspective, exact Boolean expressions of differentials over a cryptographic primitive can be conveniently established, thus verifying a given DC is naturally a Boolean satisfiability problem (SAT problem). With this observation, our approach simulates the round function of the target cipher symbolically and derives a set of Boolean equations in Algebraic Normal Form (ANF). These Boolean equations can be solved by off-the-shelf SAT solvers such as Bosphorus, which accept ANFs as their input. To demonstrate the power of our new tool, we apply it to Gimli, Ascon, and Xoodoo. For Gimli, we improve the efficiency of searching for a valid 8-round colliding DC compared with the previous MILP model (CRYPTO 2020). Our approach takes about one minute to find a valid 8-round DC, while the previous MILP model could not find any such DCs in practical time. Based on this DC, a practical semi-free-start collision attack on the intermediate 8-round Gimli-Hash is thus successfully mounted, i.e., a colliding message pair is found. For Ascon, we check several DCs reported at FSE 2021. Firstly, we verify a 2-round DC used in the collision attack on Ascon-Hash by giving a right pair (such a right pair requires $2^{156}$ attempts to find in a random search). Secondly, a 4-round differential used in the forgery attack on Ascon-128’s iteration phase is proven invalid, as a result, the corresponding forgery attack is invalid, too. For Xoodoo, we verify tens of thousands of 3-round DCs and two 4-round DCs extended from the so-called differential trail cores found by the designers or our search tool. We find all of these DCs are valid, which well demonstrates the sound independence of the differential propagation over Xoodoo’s round functions. Besides, as an independent interest, we develop a SAT-based automatic search toolkit called XoodooSat to search for 2-, 3-, and 4-round differential trail cores of Xoodoo. Our toolkit finds two more 3-round differential trail cores of weight 48 that were missed by the designers which enhance the security analysis of Xoodoo.
Last updated:  2022-11-29
Differential Meet-In-The-Middle Cryptanalysis
Christina Boura, Nicolas David, Patrick Derbez, Gregor Leander, and María Naya-Plasencia
In this paper we introduce the differential-meet-in-the-middle framework, a new cryptanalysis technique against symmetric primitives. The idea of this new cryptanalysis method consists in combining into one attack techniques from both meet-in-the-middle and differential cryptanalysis. The introduced technique can be seen as a way of extending meet-in-the-middle attacks and their variants but also as a new way to perform the key recovery part in differential attacks. We provide a simple tool to search, given a differential, for efficient applications of this new attack and apply our approach, in combination with some additional techniques, to SKINNY-128-384. Our attack on SKINNY-128-384 permits to break 25 out of the 56 rounds of this variant and improves by two rounds the previous best known attacks in the single key model.
Last updated:  2022-11-24
Post-Quantum Hybrid KEMTLS Performance in Simulated and Real Network Environments
Alexandre Augusto Giron, João Pedro Adami do Nascimento, Ricardo Custódio, and Lucas Pandolfo Perin
Adopting Post-Quantum Cryptography (PQC) in network protocols is a challenging subject. Larger PQC public keys and signatures can significantly slow the Transport Layer Security (TLS) protocol. In this context, KEMTLS is a promising approach that replaces the handshake signatures by using PQC Key Encapsulation Mechanisms (KEMs), which have, in general, smaller sizes. However, for broad PQC adoption, hybrid cryptography has its advantages over PQC-only approaches, mainly about the confidence in the security of existing cryptographic schemes. This work brings hybrid cryptography to the KEMTLS and KEMTLS-PDK protocols. We analyze different network conditions and show that the penalty when using Hybrid KEMTLS over PQC-only KEMTLS is minor under certain security levels. We also compare Hybrid KEMTLS with a hybrid version of PQTLS. Overall, the benefits of using hybrid protocols outweigh the slowdown penalties in higher security parameters, which encourages its use in practice.
Last updated:  2022-11-24
The Security of Quasigroups Based Substitution Permutation Networks
George Teseleanu
The study of symmetric structures based on quasigroups is relatively new and certain gaps can be found in the literature. In this paper, we want to fill one of these gaps. More precisely, in this work we study substitution permutation networks based on quasigroups that make use of permutation layers that are non-linear relative to the quasigroup operation. We prove that for quasigroups isotopic with a group $\mathbb{G}$, the complexity of mounting a differential attack against this type of substitution permutation network is the same as attacking another symmetric structure based on $\mathbb{G}$. The resulting structure is interesting and new, and we hope that it will form the basis for future secure block ciphers.
Last updated:  2022-11-24
Polynomial-Time Cryptanalysis of the Subspace Flooding Assumption for Post-Quantum $i\mathcal{O}$
Aayush Jain, Huijia Lin, Paul Lou, and Amit Sahai
Indistinguishability Obfuscation $(i\mathcal{O})$ is a highly versatile primitive implying a myriad advanced cryptographic applications. Up until recently, the state of feasibility of $i\mathcal{O}$ was unclear, which changed with works (Jain-Lin-Sahai STOC 2021, Jain-Lin-Sahai Eurocrypt 2022) showing that $i\mathcal{O}$ can be finally based upon well-studied hardness assumptions. Unfortunately, one of these assumptions is broken in quantum polynomial time. Luckily, the line work of Brakerski et al. Eurocrypt 2020, Gay-Pass STOC 2021, Wichs-Wee Eurocrypt 2021, Brakerski et al. ePrint 2021, Devadas et al. TCC 2021 simultaneously created new pathways to construct $i\mathcal{O}$ with plausible post-quantum security from new assumptions, namely a new form of circular security of LWE in the presence of leakages. At the same time, effective cryptanalysis of this line of work has also begun to emerge (Hopkins et al. Crypto 2021). It is important to identify the simplest possible conjectures that yield post-quantum $i\mathcal{O}$ and can be understood through known cryptanalytic tools. In that spirit, and in light of the cryptanalysis of Hopkins et al., recently Devadas et al. gave an elegant construction of $i\mathcal{O}$ from a fully-specified and simple-to-state assumption along with a thorough initial cryptanalysis. Our work gives a polynomial-time distinguisher on their "final assumption" for their scheme. Our algorithm is extremely simple to describe: Solve a carefully designed linear system arising out of the assumption. The argument of correctness of our algorithm, however, is nontrivial. We also analyze the "T-sum" version of the same assumption described by Devadas et. al. and under a reasonable conjecture rule out the assumption for any value of $T$ that implies $i\mathcal{O}$.
Last updated:  2022-11-24
Threshold Signatures with Private Accountability
Dan Boneh and Chelsea Komlo
Existing threshold signature schemes come in two flavors: (i) fully private, where the signature reveals nothing about the set of signers that generated the signature, and (ii) accountable, where the signature completely identifies the set of signers. In this paper we propose a new type of threshold signature, called TAPS, that is a hybrid of privacy and accountability. A TAPS signature is fully private from the public's point of view. However, an entity that has a secret tracing key can trace a signature to the threshold of signers that generated it. A TAPS makes it possible for an organization to keep its inner workings private, while ensuring that signers are accountable for their actions. We construct a number of TAPS schemes. First, we present a generic construction that builds a TAPS from any accountable threshold signature. This generic construction is not efficient, and we next focus on efficient schemes based on standard assumptions. We build two efficient TAPS schemes (in the random oracle model) based on the Schnorr signature scheme. We conclude with a number of open problems relating to efficient TAPS.
Last updated:  2022-11-24
FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption
Michiel Van Beirendonck, Jan-Pieter D'Anvers, and Ingrid Verbauwhede
Fully Homomorphic Encryption is a technique that allows computation on encrypted data. It has the potential to drastically change privacy considerations in the cloud, but high computational and memory overheads are preventing its broad adoption. TFHE is a promising Torus-based FHE scheme that heavily relies on bootstrapping, the noise-removal tool that must be invoked after every encrypted gate computation. We present FPT, a Fixed-Point FPGA accelerator for TFHE bootstrapping. FPT is the first hardware accelerator to heavily exploit the inherent noise present in FHE calculations. Instead of double or single-precision floating-point arithmetic, it implements TFHE bootstrapping entirely with approximate fixed-point arithmetic. Using an in-depth analysis of noise propagation in bootstrapping FFT computations, FPT is able to use noise-trimmed fixed-point representations that are up to 50% smaller than prior implementations using floating-point or integer FFTs. FPT's microarchitecture is built as a streaming processor inspired by traditional streaming DSPs: it instantiates high-throughput computational stages that are directly cascaded, with simplified control logic and routing networks. We explore different throughput-balanced compositions of streaming kernels with a user-configurable streaming width in order to construct a full bootstrapping pipeline. FPT's streaming approach allows 100% utilization of arithmetic units and requires only small bootstrapping key caches, enabling an entirely compute-bound bootstrapping throughput of 1 BS / 35$\mu$s. This is in stark contrast to the established classical CPU approach to FHE bootstrapping acceleration, which tends to be heavily memory and bandwidth-constrained. FPT is fully implemented and evaluated as a bootstrapping FPGA kernel for an Alveo U280 datacenter accelerator card. FPT achieves almost three orders of magnitude higher bootstrapping throughput than existing CPU-based implementations, and 2.5$\times$ higher throughput compared to recent ASIC emulation experiments.
Last updated:  2022-11-24
Division of Regulatory Power: Collaborative Regulation for Privacy-Preserving Blockchains
Tianyu Zhaolu, Zhiguo Wan, and Huaqun Wang
Recently, fast advances in decentralized blockchains have led to the rapid development of decentralized payment systems and finance. In decentralized anonymous payment systems such as Monero, Zerocash and Zether, payment amounts and traders' addresses are confidential to other users. Therefore, cryptocurrency may be used for illegal activities such as money laundering, bribery and blackmails. To solve this problem, some decentralized anonymous payment schemes supporting regulation have been proposed. Unfortunately, most solutions have no restriction on the regulator's power, which may lead to abuse of power and disclosure of privacy. In this paper, we propose a decentralized anonymous payment scheme supporting collaborative regulation. Different from existing solutions, our scheme prevents abuse of power by dividing the regulatory power into two regulatory authorities. These two regulatory authorities, namely Filter and Supervisor, can cooperate to recover payment amounts and traders' addresses from suspicious transactions. However, neither Filter nor Supervisor alone can decode transactions to obtain transaction privacy. Our scheme enjoys three major advantages over others: 1) We design a generic transaction structure using zk-SNARK, 2) divide regulatory power using the regulation label, 3) and achieve aggregability of transaction amounts using the amount label. The experimental result shows that the time cost of generating a transaction is about 11 s and the transaction fee is about 12,183k gas, which is acceptable.
Last updated:  2022-11-24
Vortex : Building a Lattice-based SNARK scheme with Transparent Setup
Alexandre Belling and Azam Soleimanian
We present the first transparent and plausibly post-quantum SNARK relying on the Ring Short Integer Solution problem (Ring-SIS), a well-known assumption from lattice-based cryptography. At its core, our proof system relies on a new linear-commitment scheme named Vortex which is inspired from the work of Orion and Brakedown. Vortex uses a hash function based on Ring-SIS derived from “SWIFFT" (Lyubashevsky et al., FSE08). We take advantage of the linear structure of this particular hash function to craft an efficient self-recursion technique. Although Vortex proofs have $O(\sqrt{n})$ size in the witness size, we show how our self-recursion technique can be used to build a SNARK scheme based on Vortex. The resulting SNARK works over any field with reasonably large 2-adicity (also known as FFT-friendly fields). Moreover, we introduce Wizard-IOP, an extension of the concept of polynomial-IOP. Working with Wizard-IOP rather than separate polynomial-IOPs provides us with a strong tool for handling a wide class of queries, needed for proving the correct executions of the complex state machines (e.g., zk-EVM as our use-case) efficiently and conveniently.
Last updated:  2022-11-24
Cryptography with Weights: MPC, Encryption and Signatures
Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, and Yinuo Zhang
The security of several cryptosystems rests on the trust assumption that a certain fraction of the parties are honest. This trust assumption has enabled a diverse of cryptographic applications such as secure multiparty computation, threshold encryption, and threshold signatures. However, current and emerging practical use cases suggest that this paradigm of one-person-one-vote is outdated. In this work, we consider {\em weighted} cryptosystems where every party is assigned a certain weight and the trust assumption is that a certain fraction of the total weight is honest. This setting can be translated to the standard setting (where each party has a unit weight) via virtualization. However, this method is quite expensive, incurring a multiplicative overhead in the weight. We present new weighted cryptosystems with significantly better efficiency. Specifically, our proposed schemes incur only an {\em additive} overhead in weights. \begin{itemize} \item We first present a weighted ramp secret-sharing scheme where the size of the secret share is as short as $O(w)$ (where $w$ corresponds to the weight). In comparison, Shamir's secret sharing with virtualization requires secret shares of size $w\cdot\lambda$, where $\lambda=\log |\mathbb{F}|$ is the security parameter. \item Next, we use our weighted secret-sharing scheme to construct weighted versions of (semi-honest) secure multiparty computation (MPC), threshold encryption, and threshold signatures. All these schemes inherit the efficiency of our secret sharing scheme and incur only an additive overhead in the weights. \end{itemize} Our weighted secret-sharing scheme is based on the Chinese remainder theorem. Interestingly, this secret-sharing scheme is {\em non-linear} and only achieves statistical privacy. These distinct features introduce several technical hurdles in applications to MPC and threshold cryptosystems. We resolve these challenges by developing several new ideas.
Last updated:  2022-12-01
Enhancing Ring-LWE Hardness using Dedekind Index Theorem
Charanjit S Jutla and Chengyu Lin
In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the additional algebraic structure of ideals of Dedekind domains leaves open the possibility that such ideal lattices are not as hard as general lattices. We now show that for any number field $\mathbb{Q}[X]/(f(X))$, for all prime integers $p$ such that the factorization of $f(X)$ modulo $p$ passes the Dedekind index theorem criterion, which is almost all $p$, we can base $p$-power RLWE in the polynomial ring $\mathbb{Z}[X]/(f(X))$ itself and its hardness on hardness of ideal lattices of this ring. This ring can potentially be a strict sub-ring of the ring of integers of the field, and hence not be a Dedekind domain. We also give natural examples, and prove that certain ideals require at least three generators, as opposed to two sufficient for Dedekind domains. Such rings also do not satisfy many other algebraic properties of Dedekind domains such as ideal invertibility. Our proof technique is novel as it builds an algebraic theory for general such rings that also include cyclotomic rings.
Last updated:  2022-12-02
Finding Collisions for Round-Reduced Romulus-H
Marcel Nageler, Felix Pallua, and Maria Eichlseder
Romulus-H is a hash function that currently competes as a finalist in the NIST Lightweight Cryptography competition. It is based on the Hirose DBL construction which is provably secure when used with an ideal block cipher. However, in practice, ideal block ciphers can only be approximated. The security of concrete instantiations must be cryptanalyzed carefully; the security margin may be higher or lower than in the secret-key setting. So far, the Hirose DBL construction has been studied with only a few other block ciphers, like IDEA and AES. However, Romulus-H uses Hirose DBL with the SKINNY block cipher where only very little analysis has been published so far. In this work, we present the first practical analysis of Romulus-H. We propose a new framework for finding collisions in hash functions based on the Hirose DBL construction. This is in contrast to previous work that only focused on free-start collisions. Our framework is based on the idea of joint differential characteristics which capture the relationship between the two block cipher calls in the Hirose DBL construction. To identify good joint differential characteristics, we propose a combination of a MILP and CP model. Then, we use these characteristics in another CP model to find collisions. Finally, we apply this framework to Romulus-H and find practical collisions of the hash function for 10 out of 40 rounds and practical semi-free-start collisions up to 14 rounds.
Last updated:  2022-11-23
Temporary Block Withholding Attacks on Filecoin's Expected Consensus
Tong Cao and Xin Li
As of 28 January 2022, Filecoin is ranked as the first capitalized storage-oriented cryptocurrency. In this system, miners dedicate their storage space to the network and verify transactions to earn rewards. Nowadays, Filecoin's network capacity has surpassed 15 exbibytes. In this paper, we propose three temporary block withholding attacks to challenge Filecoin's expected consensus (EC). Specifically, we first deconstruct EC following old-fashioned methods (which have been widely developed since 2009) to analyze the advantages and disadvantages of EC's design. We then present three temporary block withholding schemes by leveraging the shortcomings of EC. We build Markov Decision Process (MDP) models for the three attacks to calculate the adversary's gains. We develop Monte Carlo simulators to mimic the mining strategies of the adversary and other miners and indicate the impacts of the three attacks on expectation. As a result, we show that our three attacks have significant impacts on Filecoin's mining fairness and transaction throughput. For instance, when honest miners who control more than half the global storage power assemble their tipsets after the default transmission cutoff time, an adversary with 1% of the global storage power is able to launch temporary block withholding attacks without a loss in revenue, which is rare in existing blockchains. Finally, we discuss the implications of our attacks and propose several countermeasures to mitigate them.
Last updated:  2022-11-22
Analyzing the Leakage Resistance of the NIST's Lightweight Crypto Competition's Finalists
Corentin Verhamme, Gaëtan Cassiers, and François-Xavier Standaert
We investigate the security of the NIST Lightweight Crypto Competition’s Finalists against side-channel attacks. We start with a mode-level analysis that allows us to put forward three candidates (As- con, ISAP and Romulus-T) that stand out for their leakage properties and do not require a uniform protection of all their computations thanks to (expensive) implementation-level countermeasures. We then implement these finalists and evaluate their respective performances. Our results confirm the interest of so-called leveled implementations (where only the key derivation and tag generation require security against differential power analysis). They also suggest that these algorithms differ more by their qualitative features (e.g., two-pass designs to improve confidentiality with decryption leakage vs. one-pass designs, flexible overheads thanks to masking vs. fully mode-level, easier to implement, schemes) than by their quantitative features, which all improve over the AES and are quite sensitive to security margins against cryptanalysis.
Last updated:  2022-11-22
The Random Fault Model
Siemen Dhooghe
In this work, we introduce a more advanced fault adversary inspired from the random probing model, called the random fault model, where the adversary can fault all values in the algorithm but where the probability for each fault to occur is limited. The new adversary model is used to evaluate the security of side-channel and fault countermeasures such as Boolean masking, inner product masking, error detection techniques, error correction techniques, multiplicative tags, and shuffling methods. The results of the security analysis reveal novel insights including: error correction providing little security when faults target more bits; the order between masking and duplication providing a trade-off between side-channel and fault security; and inner product masking and multiplicative masking providing exponential protection in the field size. Moreover, the results also explain the experimental results from CHES 2022 and find weaknesses in the shuffling method from SAMOS 2021.
Last updated:  2022-11-24
MinRoot: Candidate Sequential Function for Ethereum VDF
Dmitry Khovratovich, Mary Maller, and Pratyush Ranjan Tiwari
We present a candidate sequential function for a VDF protocol to be used within the Ethereum ecosystem. The new function, called MinRoot, is an optimized iterative algebraic transformation and is a strict improvement over competitors VeeDo and Sloth++. We analyze various attacks on sequentiality and suggest weakened versions for public scrutiny. We also announce bounties on certain research directions in cryptanalysis.
Last updated:  2022-11-25
Efficient Threshold FHE with Application to Real-Time Systems
Siddhartha Chowdhury, Sayani Sinha, Animesh Singh, Shubham Mishra, Chandan Chaudhary, Sikhar Patranabis, Pratyay Mukherjee, Ayantika Chatterjee, and Debdeep Mukhopadhyay
Threshold Fully Homomorphic Encryption (ThFHE) enables arbitrary computation over encrypted data while keeping the decryption key to be distributed across multiple parties at all time. ThFHE is a key enabler for threshold cryptography and, more generally, secure distributed computing. Existing ThFHE schemes inherently require highly inefficient parameters and are unsuitable for practical deployment. In this paper, we take the first step towards to make ThFHE practically usable by (i) proposing a novel ThFHE scheme with a new analysis resulting in significantly improved parameters; (ii) and providing the first ThFHE implementation benchmark based on Torus FHE. • We propose the first ThFHE scheme with a polynomial modulus-to-noise ratio that supports practically efficient parameters while retaining provable security based on standard quantum-safe assumptions. We achieve this via a novel Rényi divergence-based security analysis of our proposed threshold decryption mechanism. • We present a highly optimized software implementation of our proposed ThFHE scheme that builds upon the existing Torus FHE library and supports (distributed) decryption on highly resource-constrained ARM-based handheld devices. To the best of our knowledge, this is the first practically efficient implementation of any ThFHE scheme. Along the way, we implement several extensions to the Torus FHE library, including a Torus-based linear integer secret sharing subroutine to support ThFHE key sharing and distributed decryption for any threshold access structure. We illustrate the efficacy of our proposal via an end-to-end use case involving encrypted computations over a real medical database, and distributed decryptions of the computed result on resource-constrained handheld devices.
Last updated:  2022-11-22
Algorithms for switching between block-wise and arithmetic masking
Evgeny Alekseev and Andrey Bozhko
Last updated:  2022-11-21
WOTSwana: A Generalized Sleeve Construction for Multiple Proofs of Ownership
David Chaum, Mario Larangeira, and Mario Yaksetig
The $\mathcal{S}_{leeve}$ construction proposed by Chaum et al. (ACNS'21) introduces an extra security layer for digital wallets by allowing users to generate a "back up key" securely nested inside the secret key of a signature scheme, i.e., ECDSA. The "back up key", which is secret, can be used to issue a "proof of ownership", i.e., only the real owner of this secret key can generate a single proof, which is based on the WOTS+ signature scheme. The authors of $\mathcal{S}_{leeve}$ proposed the formal technique for a single proof of ownership, and only informally outlined a construction to generalize it to multiple proofs. This work identifies that their proposed construction presents drawbacks, i.e., varying of signature size and signing/verifying computation complexity, limitation of linear construction, etc. Therefore we introduce WOTSwana, a generalization of $\mathcal{S}_{leeve}$, which is, more concretely, a more general scheme, i.e., an extra security layer that generates multiple proofs of ownership, and put forth a thorough formalization of two constructions: (1) one given by a linear concatenation of numerous WOTS+ private/public keys, and (2) a construction based on tree like structure, i.e., an underneath Merkle tree whose leaves are WOTS+ private/public key pairs. Furthermore, we present the security analysis for multiple proofs of ownership, showcasing that this work addresses the early mentioned drawbacks of the original construction. In particular, we extend the original security definition for $\mathcal{S}_{leeve}$. Finally, we illustrate an alternative application of our construction, by discussing the creation of an encrypted group chat messaging application.
Last updated:  2022-12-01
Anonymous Tokens with Hidden Metadata Bit from Algebraic MACs
F. Betül Durak, Serge Vaudenay, and Melissa Chase
On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish honest users from bots or attackers. In this work, we focus on designing an anonymous token protocol between a client and an issuer (also a verifier) that enables the issuer to support its fraud detection mechanisms while preserving users' privacy. This is done by allowing the issuer to embed a hidden (from the client) metadata bit into the tokens. We first study an existing protocol from CRYPTO 2020 which is an extension of Privacy Pass from PoPETs 2018; that protocol aimed to provide support for a hidden metadata bit, but provided a somewhat restricted security notion. We demonstrate a new attack, showing that this is a weakness of the protocol, not just the definition. In particular, the metadata bit hiding is weak in the setting where the attacker can redeem some tokens and get feedback on what bit is extracted. We then revisit the formalism of anonymous tokens with private metadata bit, consider the more natural notion, and design a scheme which achieves it. In order to design this new secure protocol, we base our construction on algebraic MACs instead of PRFs. Our security definitions capture a realistic threat model where adversaries could, through direct feedback or side channels, learn the embedded bit when the token is redeemed. Finally, we compare our protocol with one of the CRYPTO 2020 protocols which we obtain 20\% more efficient implementation.
Last updated:  2022-11-21
cuXCMP: CUDA-Accelerated Private Comparison Based on Homomorphic Encryption
Hao Yang, Shiyu Shen, Zhe Liu, and Yunlei Zhao
Private comparison schemes constructed on homomorphic encryption oﬀer the noninteractive, output expressive and parallelizable features, and have advantages in communication bandwidth and performance. In this paper, we propose cuXCMP, which allows negative and ﬂoat inputs, oﬀers fully output expressive feature, and is more extensible and practical compared to XCMP (AsiaCCS 2018). Meanwhile, we introduce several memory-centric optimizations of the constant term extraction kernel tailored for CUDA-enabled GPUs. Firstly, we fully utilize the shared memory and present compact GPU implementations of NTT and INTT using a single block; Secondly, we fuse multiple kernels into one AKS kernel, which conducts the automorphism and key switching operation, and reduce the grid dimension for better resource usage, data access rate and synchronization. Thirdly, we precisely measure the IO latency and choose an appropriate number of CUDA streams to enable concurrent execution of independent operations, yielding a constant term extraction kernel with perfect latency hide, i.e., CTX. Combining these approaches, we boost the overall execution time to optimum level and the speedup ratio increases with the comparison scales. For one comparison, we speedup the AKS by 23.71×, CTX by 15.58×, and scheme by 1.83× (resp., 18.29×, 11.75×, and 1.42×) compared to C (resp., AVX512) baselines, respectively. For 32 comparisons, our CTX and scheme implementations outperform the C (resp., AVX512) baselines by 112.00× and 1.99× (resp., 81.53× and 1.51×).
Last updated:  2022-11-21
Another Round of Breaking and Making Quantum Money: How to Not Build It from Lattices, and More
Hart Montgomery, Jiahui Liu, and Mark Zhandry
Public verification of quantum money has been one of the central objects in quantum cryptography ever since Wiesner's pioneering idea of using quantum mechanics to construct banknotes against counterfeiting. So far, we do not know any publicly-verifiable quantum money scheme that is provably secure from standard assumptions. In this work, we provide both negative and positive results for publicly verifiable quantum money. **In the first part, we give a general theorem, showing that a certain natural class of quantum money schemes from lattices cannot be secure. We use this theorem to break the recent quantum money scheme of Khesin, Lu, and Shor. **In the second part, we propose a framework for building quantum money and quantum lightning we call invariant money which abstracts some of the ideas of quantum money from knots by Farhi et al.(ITCS'12). In addition to formalizing this framework, we provide concrete hard computational problems loosely inspired by classical knowledge-of-exponent assumptions, whose hardness would imply the security of quantum lightning, a strengthening of quantum money where not even the bank can duplicate banknotes. **We discuss potential instantiations of our framework, including an oracle construction using cryptographic group actions and instantiations from rerandomizable functional encryption, isogenies over elliptic curves, and knots.
Last updated:  2022-11-21
The Performance Analysis of Post-Quantum Cryptography for Vehicular Communications
Abel C. H. Chen
For avoding the attacks from quantum computing (QC), this study applies the post-quantum cryptography (PQC) methods without hidden subgroups to the security of vehicular communications. Due the mainstream technologies of PQC methods (i.e. lattice-based cryptography methods), the standard digital signature methods including Dilithium and Falcon have been discussed and compared. This study uses a queueing model to analyze the performance of these standard digital signature methods for selection decision-making.
Last updated:  2022-11-20
Witness-Succinct Universally-Composable SNARKs
Chaya Ganesh, Yashvanth Kondi, Claudio Orlandi, Mahak Pancholi, Akira Takahashi, and Daniel Tschudi
Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) are becoming an increasingly fundamental tool in many real-world applications where the proof compactness is of the utmost importance, including blockchains. A proof of security for SNARKs in the Universal Composability (UC) framework (Canetti, FOCS'01) would rule out devastating malleability attacks. To retain security of SNARKs in the UC model, one must show their simulation-extractability such that the knowledge extractor is both black-box and straight-line, which would imply that proofs generated by honest provers are non-malleable. However, existing simulation-extractability results on SNARKs either lack some of these properties, or alternatively have to sacrifice witness succinctness to prove UC security. In this paper, we provide a compiler lifting any simulation-extractable NIZKAoK into a UC-secure one in the global random oracle model, importantly, while preserving the same level of witness succinctness. Combining this with existing zkSNARKs, we achieve, to the best of our knowledge, the first zkSNARKs simultaneously achieving UC-security and constant sized proofs.
Last updated:  2022-11-21
A New Higher Order Differential of RAGHAV
Naoki Shibayama and Yasutaka Igarashi
RAGHAV is a 64-bit block cipher proposed by Bansod in 2021. It supports 80-, and 128-bit secret keys. The designer evaluated its security against typical attack, such as differential cryptanalysis, linear cryptanalysis, and so on. On the other hand, it has not been reported the security of RAGHAV against higher order differential attack, which is one of the algebraic attacks. In this paper, we applied higher order differential cryptanalysis to RAGHAV. As a results, we found a new full-round higher order characteristic of RAGHAV using 1-st order differential. Exploiting this characteristic, we also show that the full-round of RAGHAV is attackable by distinguishing attack with 2 chosen plaintexts.
Last updated:  2022-11-20
Secret Sharing for Generic Access Structures
James Smith
Sharing a secret efficiently amongst a group of participants is not easy since there is always an adversary / eavesdropper trying to retrieve the secret. In secret sharing schemes, every participant is given a unique share. When the desired group of participants come together and provide their shares, the secret is obtained. For other combinations of shares, a garbage value is returned. A threshold secret sharing scheme was proposed by Shamir and Blakeley independently. In this (n,t) threshold secret sharing scheme, the secret can be obtained when at least $t$ out of $n$ participants contribute their shares. This paper proposes a novel algorithm to reveal the secret only to the subsets of participants belonging to the access structure. This scheme implements totally generalized ideal secret sharing. Unlike threshold secret sharing schemes, this scheme reveals the secret only to the authorized sets of participants, not any arbitrary set of users with cardinality more than or equal to $t$. Since any access structure can be realized with this scheme, this scheme can be exploited to implement various access priorities and access control mechanisms. A major advantage of this scheme over the existing ones is that the shares being distributed to the participants is totally independent of the secret being shared. Hence, no restrictions are imposed on the scheme and it finds a wider use in real world applications.
Last updated:  2022-11-20
Efficient Methods for Implementation of Generalized Access Structures
James Smith
The recent advent of cloud computing and IoT has made it imperative to store huge amount of data in the cloud servers. Enormous amount of data is also stored in the servers of big organizations. In organizations, it is not desirable for every member to have equal privileges to access the stored data. Threshold secret sharing schemes are widely used for implementing such access control mechanisms. The access privileges of the members also vary from one data packet to another. While implementing such dynamic access structures using threshold secret sharing schemes, the key management becomes too complex to be implemented in real time. Furthermore, the storage of the users’ access privileges requires exponential space (O($2^n$)) and its implementation requires exponential time. In this paper, the algorithms proposed to tackle the problems of priority based access control and authentication require a space complexity of O($n^2$) and a time complexity of O($n$), where n is the number of users. In the practical scenario, such space can easily be provided on the servers and the algorithms can run smoothly in real time.
Last updated:  2022-11-19
Throughput Limitation of the Off-chain Payment Networks
Shayan Hamidi Dehshali, Seyed Mahdi Hosseini, Soheil Zibakhsh Shabgahi, and Behnam Bahrak
Off-chain payment channels were introduced as one of the solutions to the blockchain scalability problem. The channels shape a network, where parties have to lock funds for their creation. A channel is expected to route a limited number of transactions before it becomes unbalanced, when all of the funds are devoted to one of the parties. Since an on-chain transaction is often necessary to establish, rebalance, or close a channel, the off-chain network is bounded to the throughput of the blockchain. In this paper, we propose a mathematical model to formulate limitation on the throughput of an off-chain payment network. As a case study, we show the limitation of the Lightning Network, in comparison with popular banking systems. Our results show that theoretically, the throughput of the Lightning Network can reach the order of 10000 transactions per second, close to the average throughput of centralized banking systems.
Last updated:  2022-11-19
Classic McEliece Key Generation on RAM constrained devices
Rainer Urian and Raphael Schermann
Classic McEliece is a code based encryption scheme and candidate of the NIST post quantum contest. Implementing Classic McEliece on smart card chips is a challenge, because those chips have only a very limited amount of RAM. Decryption is not an issue because the cryptogram size is short and the decryption algorithm can be implemented using very few RAM. However key generation is a concern, because a large binary matrix must be inverted. In this paper, we show how key generation can be done on smart card chips with very little RAM resources. This is accomplished by modifying the key generation algorithm and splitting it in a security critical part and a non security critical part. The security critical part can be implemented on the smart card controller. The non critical part contains the matrix inversion and will be done on a connected host.
Last updated:  2022-11-18
On Black-Box Constructions of Time and Space Efficient Sublinear Arguments from Symmetric-Key Primitives
Laasya Bangalore, Rishabh Bhadauria, Carmit Hazay, and Muthuramakrishnan Venkitasubramaniam
Zero-knowledge proofs allow a prover to convince a verifier of a statement without revealing anything besides its validity. A major bottleneck in scaling sub-linear zero-knowledge proofs is the high space requirement of the prover, even for NP relations that can be verified in a small space. In this work, we ask whether there exist complexity-preserving (i.e. overhead w.r.t time and space are minimal) succinct zero-knowledge arguments of knowledge with minimal assumptions while making only black-box access to the underlying primitives. We design the first such zero-knowledge system with sublinear communication complexity (when the underlying $\textsf{NP}$ relation uses non-trivial space) and provide evidence why existing techniques are unlikely to improve the communication complexity in this setting. Namely, for every NP relation that can be verified in time T and space S by a RAM program, we construct a public-coin zero-knowledge argument system that is black-box based on collision-resistant hash-functions (CRH) where the prover runs in time $\widetilde{O}(T)$ and space $\widetilde{O}(S)$, the verifier runs in time $\widetilde{O}(T/S+S)$ and space $\widetilde{O}(1)$ and the communication is $\widetilde{O}(T/S)$, where $\widetilde{O}()$ ignores polynomial factors in $\log T$ and $\kappa$ is the security parameter. As our construction is public-coin, we can apply the Fiat-Shamir heuristic to make it non-interactive with sample communication/computation complexities. Furthermore, we give evidence that reducing the proof length below $\widetilde{O}(T/S)$ will be hard using existing symmetric-key based techniques by arguing the space-complexity of constant-distance error correcting codes.
Last updated:  2022-11-30
Efficient Aggregatable BLS Signatures with Chaum-Pedersen Proofs
Jeff Burdges, Oana Ciobotaru, Syed Lavasani, and Alistair Stewart
BLS signatures have fast aggregated signature verification but slow individual signature verification. We propose a three part optimisation that dramatically reduces CPU time in large distributed system using BLS signatures: First, public keys should be given on both source groups $\mathbb{G}_1$ and $\mathbb{G}_2$, with a proof-of-possession check for correctness. Second, aggregated BLS signatures should carry their particular aggregate public key in $\mathbb{G}_2$, so that verifiers can do both hash-to-curve and aggregate public key checks in $\mathbb{G}_1$. Third, individual non-aggregated BLS signatures should carry short Chaum-Pedersen DLEQ proofs of correctness, so that verifying individual signatures no longer requires pairings, which makes their verification much faster. We prove security for these optimisations. The proposed scheme is implemented and benchmarked to compare with classic BLS scheme.
Last updated:  2022-12-02
ADMM and Reproducing Sum-Product Decoding Algorithm Applied to QC-MDPC Code-based McEliece Cryptosystems
Kohtaro Watanabe, Motonari Ohtsuka, and Yuta Tsukie
QC-MDPC (quasi cyclic moderate density parity check) code-based McEliece cryptosystems are considered to be one of the candidates for post-quantum cryptography. Decreasing DER (decoding error rate) is one of important factor for their security, since recent attacks to these cryptosystems effectively use DER information. In this paper, we pursue the possibility of optimization-base decoding, concretely we examine ADMM (alternating direction method of multipliers), a recent developing method in optimization theory. Further, RSPA (reproducing sum-product algorithm), which efficiently reuse outputs of SPA (sum-product algorithm) is proposed for the reduction of execution time in decoding. By numerical simulations, we show that the proposing scheme shows considerable decrement in DER compared to the conventional decoding methods such as BF (bit-flipping algorithm) variants or SPA.
Last updated:  2022-11-18
Forking Sums of Permutations for Optimally Secure and Highly Efficient PRFs
Avijit Dutta, Jian Guo, and Eik List
The desirable encryption scheme possesses high PRF security, high efficiency, and the ability to produce variable-length outputs. Since designing dedicated secure PRFs is difficult, a series of works was devoted to building optimally secure PRFs from the sum of independent permutations (SoP), Encrypted Davies-Meyer (EDM), its Dual (EDMD), and the Summation-Truncation Hybrid (STH) for variable output lengths, which can be easily instantiated from existing permutations. For increased efficiency, reducing the number of operations in established primitives has been gaining traction: Mennink and Neves pruned EDMD to FastPRF, and Andreeva et al. introduced ForkCiphers, which take an n-bit input, process it through a reduced-round permutation, fork it into two states, and feed each of them into another reduced-round permutation to produce a 2n-bit output. The constructions above can be used in secure variable-length modes or generalizations such as MultiForkCiphers. In this paper, we suggest a framework of those constructions in terms of the three desiderata: we span the spectrum of (1) output length vs. PRF security, (2) full vs. round-reduced primitives, and (3) fixed- vs. variable-length outputs. From this point of view, we identify remaining gaps in the spectrum and fill them with the proposal of several highly secure and efficient fixed- and variable-output-length PRFs. We fork SoP and STH to ForkPRF and ForkSTH, extend STH to the variable-output-length construction STHCENC, which bridges the gap between CTR mode and CENC,and propose ForkCENC, ForkSTHCENC, ForkEDMD, as well as ForkEDM-CTR as the variable-output-length and round-reduced versions of CENC, STH, FastPRF, and FastPRF's dual, respectively. Using recent results on Patarin's general Mirror Theory, we have proven that almost all our proposed PRFs are optimally secure under the assumption that the permutations are pairwise independent and random and STH achieves the optimal security depending on the output length. Our constructions can be highly efficient in practice. We propose efficient instantiations from round-reduced AES and back it with the cryptanalysis lessons learned from existing earlier analysis of AES-based primitives.
Last updated:  2022-11-18
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup
Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam
We design and implement a simple zero-knowledge argument protocol for $\mathsf{NP}$ whose communication complexity is proportional to the square-root of the verification circuit size. The protocol can be based on any collision-resistant hash function. Alternatively, it can be made non-interactive in the random oracle model, yielding concretely efficient zk-SNARKs that do not require a trusted setup or public-key cryptography. Our protocol is obtained by applying an optimized version of the general transformation of Ishai et al. (STOC 2007) to a variant of the protocol for secure multiparty computation of Damg$\mathring{a}$rd and Ishai (CRYPTO 2006). It can be viewed as a simple zero-knowledge interactive PCP based on interleaved'' Reed-Solomon codes. This paper is an extended version of the paper published in CCS 2017 and features a tighter analysis, better implementation along with formal proofs. For large verification circuits, the Ligero prover remains competitive against subsequent works with respect to the prover’s running time, where our efficiency advantages become even bigger in an amortized setting, where several instances need to be proven simultaneously. Our protocol is attractive not only for very large verification circuits but also for moderately large circuits that arise in applications. For instance, for verifying a SHA-256 preimage with $2^{-40}$ soundness error, the communication complexity is roughly 35KB. The communication complexity of our protocol is independent of the circuit structure and depends only on the number of gates. For $2^{-40}$ soundness error, the communication becomes smaller than the circuit size for circuits containing roughly 3 million gates or more. With our refined analysis the Ligero system's proof lengths and prover's running times are better than subsequent post-quantum ZK-SNARKs for small to moderately large circuits.
Last updated:  2022-11-17
A Universally Composable PAKE with Zero Communication Cost (And Why It Shouldn't Be Considered UC-Secure)
Lawrence Roy and Jiayu Xu
A Password-Authenticated Key Exchange (PAKE) protocol allows two parties to agree upon a cryptographic key, when the only information shared in advance is a low-entropy password. The standard security notion for PAKE (Canetti et al., Eurocrypt 2005) is in the Universally Composable (UC) framework. We show that unlike most UC security notions, UC PAKE does not imply correctness. While Canetti et al. seems to have implicitly noticed this issue, it has yet to be explicitly identified by the PAKE literature. We present a comprehensive study of correctness in UC PAKE: 1. We show that TrivialPAKE, a no-message protocol that does not satisfy correctness, is a UC PAKE; 2. We propose nine approaches to guaranteeing correctness in the UC security notion of PAKE, and show that seven of them are equivalent, whereas the other two are unachievable; 3. We prove that a direct solution, namely changing the UC PAKE functionality to incorporate correctness, is impossible; 4. Finally, we show how to naturally incorporate correctness by changing the model — we view PAKE as a three-party protocol, with the man-in-the-middle adversary as the third party. In this way, we hope to shed some light on the very nature of UC-security in the man-in-the-middle setting.
Last updated:  2022-11-17
AUC: Accountable Universal Composability
Mike Graf, Ralf Küsters, and Daniel Rausch
Accountability is a well-established and widely used security concept that allows for obtaining undeniable cryptographic proof of misbehavior, thereby incentivizing honest behavior. There already exist several general purpose accountability frameworks for formal game-based security analyses. Unfortunately, such game-based frameworks do not support modular security analyses, which is an important tool to handle the complexity of modern protocols. Universal composability (UC) models provide native support for modular analyses, including re-use and composition of security results. So far, accountability has mainly been modeled and analyzed in UC models for the special case of MPC protocols, with a general purpose accountability framework for UC still missing. That is, a framework that among others supports arbitrary protocols, a wide range of accountability properties, handling and mixing of accountable and non-accountable security properties, and modular analysis of accountable protocols. To close this gap, we propose AUC, the first general purpose accountability framework for UC models, which supports all of the above, based on several new concepts. We exemplify AUC in three case studies not covered by existing works. In particular, AUC unifies existing UC accountability approaches within a single framework.
Last updated:  2022-11-17
Sweep-UC: Swapping Coins Privately
Lucjan Hanzlik, Julian Loss, Sri AravindaKrishnan Thyagarajan, and Benedikt Wagner
Fair exchange (also referred to as atomic swap) is a fundamental operation in any cryptocurrency, that allows users to atomically exchange coins. While a large body of work has been devoted to this problem, most solutions lack on-chain privacy. Thus, coins retain a public transaction history which is known to degrade the fungibility of a currency. This has led to a flourishing line of related research on fair exchange with privacy guarantees. Existing protocols either rely on heavy scripting (which also degrades fungibility), do not support atomic swaps across a wide range currencies, or come with incomplete security proofs. To overcome these limitations, we introduce Sweep-UC (Read as Sweep Ur Coins), the first fair exchange protocol that simultaneously is efficient, minimizes scripting, and is compatible with a wide range of currencies (more than the state of the art). We build Sweep-UC from modular subprotocols and give a rigorous security analysis in the UC-framework. Many of our tools and security definitions can be used in standalone fashion and may serve as useful components for future constructions of fair exchange.
Last updated:  2022-11-17
Quantum Rebound Attacks on Reduced-Round ARIA-Based Hash Functions
Seungjun Baek and Jongsung Kim
ARIA is a block cipher proposed by Kwon et al. at ICISC 2003, and it is widely used as the national standard block cipher in the Republic of Korea. In this study, we identify some flaws in the quantum rebound attack on 7-round ARIA-DM proposed by Dou et al., and we reveal that the limit of this attack is up to 5-round. Our revised attack applies not only to ARIA-DM but also to ARIA-MMO and ARIA-MP among the PGV models, and it is valid for all key lengths of ARIA. Moreover, we present dedicated quantum rebound attacks on 7-round ARIA-Hirose and ARIA-MJH for the first time. These attacks are only valid for the 256-bit key length of ARIA because they are constructed using the degrees of freedom in the key schedule. All our attacks are faster than the generic quantum attack in the cost metric of time–space tradeoff.
Last updated:  2022-11-17
Slid Pairs of the Fruit-80 Stream Cipher
Pang Kok An, Shekh Faisal Abdul-Latip, and Hazlin Abdul Rani
Fruit is a small-state stream cipher designed for securing communications among resource-constrained devices. The design of Fruit was first known to the public in 2016. It was later improved as Fruit-80 in 2018 and becomes the latest and final version among all versions of the Fruit stream ciphers. In this paper, we analyze the Fruit-80 stream cipher. We found that Fruit-80 generates identical keystreams from certain two distinct pairs of key and IV. Such pair of key and IV pairs is known as a slid pair. Moreover, we discover that when two pairs of key and IV fulfill specific characteristics, they will generate identical keystreams. This shows that slid pairs do not always exist arbitrarily in Fruit-80. We define specific rules which are equivalent to the characteristics. Using the defined rules, we are able to automate the searching process using an MILP solver, which makes searching of the slid pairs trivial.
Last updated:  2022-12-08
Survey on Fully Homomorphic Encryption, Theory, and Applications
Chiara Marcolla, Victor Sucasas, Marc Manzano, Riccardo Bassoli, Frank H.P. Fitzek, and Najwa Aaraj
Data privacy concerns are increasing significantly in the context of Internet of Things, cloud services, edge computing, artificial intelligence applications, and other applications enabled by next generation networks. Homomorphic Encryption addresses privacy challenges by enabling multiple operations to be performed on encrypted messages without decryption. This paper comprehensively addresses homomorphic encryption from both theoretical and practical perspectives. The paper delves into the mathematical foundations required to understand fully homomorphic encryption (FHE). It consequently covers design fundamentals and security properties of FHE and describes the main FHE schemes based on various mathematical problems. On a more practical level, the paper presents a view on privacy-preserving Machine Learning using homomorphic encryption, then surveys FHE at length from an engineering angle, covering the potential application of FHE in fog computing, and cloud computing services. It also provides a comprehensive analysis of existing state-of-the-art FHE libraries and tools, implemented in software and hardware, and the performance thereof.
Last updated:  2022-11-17
Revisiting the Concrete Hardness of SelfTargetMSIS in CRYSTALS-Dilithium
Geng Wang, Wenwen Xia, Gongyu Shi, Ming Wan, Yuncong Zhang, and Dawu Gu
In this paper, we reconsider the security for CRYSTALS-Dilithium, a lattice-based post-quantum signature scheme standardized by NIST. In their documentation, the authors proved that the security of the signature scheme can be based on the hardness of the following three assumptions: MLWE, MSIS and SelfTargetMSIS. While the first two are standard lattice assumptions with hardness well studied, the authors claimed that the third assumption SelfTargetMSIS can be estimated by the hardness of MSIS (and further into SIS). However, we point out that this is in fact not the case. We give a new algorithm for solving SelfTargetMSIS, by both experimental results and asymptotic complexities, we prove that under specific parameters, solving SelfTargetMSIS might be faster than MSIS. Although our algorithm does not propose a real threat to parameters used in Dilithium, we successfully show that solving SelfTargetMSIS cannot be turned into solving MSIS or MISIS. Furthermore, we define a new variant of MISIS, called sel-MISIS, and show that solving SelfTargetMSIS can only be turned into solving sel-MISIS. We believe that in order to fully understand the concrete hardness of SelfTargetMSIS and prevent potential attacks to Dilithium, the hardness of this new problem needs to be further studied.
Last updated:  2022-11-16
Secret-Shared Joins with Multiplicity from Aggregation Trees
Saikrishna Badrinarayanan, Sourav Das, Gayathri Garimella, Srinivasan Raghuraman, and Peter Rindal
We present novel protocols to compute SQL-like join operations on secret shared database tables with non-unique join keys. Previous approaches to the problem had the restriction that the join keys of both the input tables must be unique or had quadratic overhead. Our work lifts this restriction, allowing one or both of the secret shared input tables to have an unknown and unbounded number of repeating join keys while achieving efficient $O(n\log n)$ asymptotic communication/computation and $O(\log n)$ rounds of interaction, independent of the multiplicity of the keys. We present two join protocols, \ProtoUni and \ProtoDup. The first, \ProtoUni is optimized for the case where one table has a unique primary key while the second, \ProtoDup is for the more general setting where both tables contain duplicate keys. Both protocols require $O(n \log n)$ time and $O(\log n)$ rounds to join two tables of size $n$. Our framework for computing joins requires an efficient sorting protocol and generic secure computation for circuits. We concretely instantiate our protocols in the honest majority three-party setting. Our join protocols are built around an efficient method to compute structured aggregations over a secret shared input vector $\V\in \mathbb{D}^n$. If the parties have another secret-shared vector of control bits $\B \in \{0, 1\}^n$ to partition $\V$ into sub-vectors (that semantically relates to the join operations). A structured aggregation computes a secret shared vector $\V'\in \mathbb{D}^n$ where every sub-vector $(\V_b,...,\V_e)$ (defined by the control bits) is aggregated as $\V_i'=\V_b\op...\op \V_i$ for $i\in \{b,...,e\}$ according to some user-defined operator $\op$. Critically, the $b,e$ indices that partition the vector are secret. It's trivial to compute aggregations by sequentially processing the input vector and control bits. This would require $O(n)$ rounds and would be very slow due to network latency. We introduce Aggregation Trees as a general technique to compute aggregations in $O(\log n)$ rounds. For our purpose of computing joins, we instantiate $\op \in$ \textsf{\{copy previous value, add\}}, but we believe that this technique is quite powerful and can find applications in other useful settings.
Last updated:  2022-11-16
Streaming Functional Encryption
Jiaxin Guan, Alexis Korb, and Amit Sahai
We initiate the study of streaming functional encryption (sFE) which is designed for scenarios in which data arrives in a streaming manner and is computed on in an iterative manner as the stream arrives. Unlike in a standard functional encryption (FE) scheme, in an sFE scheme, we (1) do not require the entire data set to be known at encryption time and (2) allow for partial decryption given only a prefix of the input. More specifically, in an sFE scheme, we can sequentially encrypt each data point $x_i$ in a stream of data $x = x_1\ldots x_n$ as it arrives, without needing to wait for all $n$ values. We can then generate function keys for streaming functions which are stateful functions that take as input a message $x_i$ and a state $\mathsf{st}_i$ and output a value $y_i$ and the next state $\mathsf{st}_{i+1}$. For any $k \leq n$, a user with a function key for a streaming function $f$ can learn the first $k$ output values $y_1\ldots y_k$ where $(y_i, \mathsf{st}_{i+1}) = f(x_i, \mathsf{st}_i)$ and $\mathsf{st}_1 = \bot$ given only ciphertexts for the first $k$ elements $x_1\ldots x_k$. In this work, we introduce the notion of sFE and show how to construct it from FE. In particular, we show how to achieve a secure sFE scheme for $\mathsf{P/Poly}$ from a compact, secure FE scheme for $\mathsf{P/Poly}$, where our security notion for sFE is similar to standard FE security except that we require all function queries to be made before the challenge ciphertext query. Furthermore, by combining our result with the FE construction of Jain, Lin, and Sahai (STOC, 2022), we show how to achieve a secure sFE scheme for $\mathsf{P/Poly}$ from the polynomial hardness of well-studied assumptions.
Last updated:  2022-11-16
Efficiently Testable Circuits
Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, and Krzysztof Pietrzak
In this work, we put forward the notion of efficiently testable circuits'' and provide circuit compilers that transform any circuit into an efficiently testable one. Informally, a circuit is testable if one can detect tampering with the circuit by evaluating it on a small number of inputs from some test set. Our technical contribution is a compiler that transforms any circuit $C$ into a testable circuit $(\widehat{C}, \widehat{T})$ for which we can detect arbitrary tampering with all wires in $\widehat{C}$. The notion of a testable circuit is weaker or incomparable to existing notions of tamper-resilience, which aim to detect or even correct for errors introduced by tampering during every query, but our new notion is interesting in several settings, and we achieve security against much more general tampering classes -- like tampering with all wires -- with very modest overhead. Concretely, starting from a circuit $C$ of size $n$ and depth $d$, for any $L$ (think of $L$ as a small constant, say $L=4$), we get a testable $(\widehat{C}, \widehat{T})$ where $\widehat{C}$ is of size $\approx 12n$ and depth $d+\log(n)+L\cdot n^{1/L}$. The test set $\widehat{T}$ is of size $4\cdot 2^L$. The number of extra input and output wires (i.e., pins) we need to add for the testing is $3+L$ and $2^L$, respectively.
Last updated:  2022-11-16
A Closer Look at a Recent Pipelined True Random Number Generator Design
Markus Dichtl
The paper " An energy and area efficient, all digital entropy source compatible with modern standards based on jitter pipelining", by Peetermans and Verbauwhede, IACR Transactions on Cryptographic Hardware and Embedded Systems, Aug. 2022, 88-109, suggests a pipelined TRNG design and a stochastic model for it. The stochastic model is shown to be inadequate and other problems of the TRNG design are identified. Possible fixes for the problems are considered.
Last updated:  2022-11-16
LowMS: a new rank metric code-based KEM without ideal structure
Nicolas Aragon, Victor Dyseryn, Philippe Gaborit, Pierre Loidreau, Julian Renner, and Antonia Wachter-Zeh
We propose and analyze LowMS, a new rank-based key encapsulation mechanism (KEM). The acronym stands for Loidreau with Multiple Syndromes, since our work combines the cryptosystem of Loidreau (presented at PQCrypto 2017) together with the multiple syndrome approach, that allows to reduce parameters by sending several syndromes with the same error support in one ciphertext. Our scheme is designed without using ideal structures. Considering cryptosystems without such an ideal structure, like the FrodoKEM cryptosystem, is important since structure allows to compress objects, but gives reductions to specific problems whose security may potentially be weaker than for unstructured problems. For 128 bits of security, we propose parameters with a public key size of 4,6KB and a ciphertext size of 1,1KB. To the best of our knowledge, our scheme is the smallest among all existing unstructured post-quantum lattice or code-based algorithms, when taking into account the sum of the public key size and the ciphertext size. In that sense, our scheme is for instance about 4 times shorter than FrodoKEM. Our system relies on the hardness of the Rank Support Learning problem, a well-known variant of the Rank Syndrome Decoding problem, and on the problem of indistinguishability of distorted Gabidulin codes, i.e. Gabidulin codes multiplied by an homogeneous matrix of given rank. The latter problem was introduced by Loidreau in his paper.
Last updated:  2022-11-16
Efficient Secure Three-Party Sorting with Applications to Data Analysis and Heavy Hitters
Gilad Asharov, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Ariel Nof, Benny Pinkas, Katsumi Takahashi, and Junichi Tomida
We present a three-party sorting protocol secure against passive and active adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as private set intersection of shared data, deduplication, and the identification of heavy hitters. The new protocol computes a stable sort. It is based on radix sort and is asymptotically better than previous secure sorting protocols. It improves on previous radix sort protocols by not having to shuffle the entire length of the items after each comparison step. We implemented our sorting protocol with different optimizations and achieved concretely fast performance. For example, sorting one million items with 32-bit keys and 32-bit values takes less than 2 seconds with semi-honest security and about 3.5 seconds with malicious security. Finding the heavy hitters among hundreds of thousands of 256-bit values takes only a few seconds, compared to close to an hour in previous work.
Last updated:  2022-11-16
Compact FE for Unbounded Attribute-Weighted Sums for Logspace from SXDH
Pratish Datta, Tapas Pal, and Katsuyuki Takashima
This paper presents the first functional encryption (FE) scheme for the attribute-weighted sum (AWS) functionality that supports the uniform model of computation. In such an FE scheme, encryption takes as input a pair of attributes (x,z) where the attribute x is public while the attribute z is private. A secret key corresponds to some weight function f, and decryption recovers the weighted sum f(x)z. This is an important functionality with a wide range of potential real life applications, many of which require the attribute lengths to be flexible rather than being fixed at system setup. In the proposed scheme, the public attributes are considered as binary strings while the private attributes are considered as vectors over some finite field, both having arbitrary polynomial lengths that are not fixed at system setup. The weight functions are modeled as Logspace Turing machines. Prior schemes [Abdalla, Gong, and Wee, CRYPTO 2020 and Datta and Pal, ASIACRYPT 2021] could only support non-uniform Logspace. The proposed scheme is built in asymmetric prime-order bilinear groups and is proven adaptively simulation secure under the well-studied symmetric external Diffie-Hellman (SXDH) assumption against an arbitrary polynomial number of secret key queries both before and after the challenge ciphertext. This is the best possible level of security for FE as noted in the literature. As a special case of the proposed FE scheme, we also obtain the first adaptively simulation secure inner-product FE (IPFE) for vectors of arbitrary length that is not fixed at system setup. On the technical side, our contributions lie in extending the techniques of Lin and Luo [EUROCRYPT 2020] devised for payload hiding attribute-based encryption (ABE) for uniform Logspace access policies avoiding the so-called “one-use” restriction in the indistinguishability-based security model as well as the “three-slot reduction” technique for simulation-secure attribute-hiding FE for non-uniform Logspace devised by Datta and Pal [ASIACRYPT 2021] to the context of simulation-secure attribute-hiding FE for uniform Logspace.
Last updated:  2022-11-16
Proofs of discrete logarithm equality across groups
Melissa Chase, Michele Orrù, Trevor Perrin, and Greg Zaverucha
We provide a $\Sigma$-protocol for proving that two values committed in different groups are equal. We study our protocol in Lyubashevsky's framework "Fiat-Shamir with aborts" (Asiacrypt’09) and offer concrete parameters for instantiating it. We explain how to use it to compose SNARKs with $\Sigma$-protocols, create efficient proofs of solvency on cryptocurrencies, and join of attributes across different anonymous credentials.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.