Papers updated in last 183 days (Page 14 of 1505 results)

Last updated:  2023-10-21
The One-Wayness of Jacobi Signatures
Henry Corrigan-Gibbs and David J. Wu
In this short note, we show that under a mild number-theoretic conjecture, recovering an integer from its Jacobi signature modulo $N = p^2q$, for primes $p$ and $q$, is as hard as factoring $N$.
Last updated:  2023-10-21
CENSOR: Privacy-preserving Obfuscation for Outsourcing SAT formulas
Tassos Dimitriou and Khazam Alhamdan
We propose a novel obfuscation technique that can be used to outsource hard satisfiability (SAT) formulas to the cloud. Servers with large computational power are typically used to solve SAT instances that model real-life problems in task scheduling, AI planning, circuit verification and more. However, outsourcing data to the cloud may lead to privacy and information breaches since satisfying assignments may reveal considerable information about the underlying problem modeled by SAT. In this work, we develop CENSOR (privaCy prEserviNg obfuScation for Outsourcing foRmulas), a novel SAT obfuscation framework that resembles Indistinguishability Obfuscation. At the core of the framework lies a mechanism that transforms any formula to a random one with the same number of satisfying assignments. As a result, obfuscated formulas are indistinguishable from each other thus preserving the input-output privacy of the original SAT instance. Contrary to prior solutions that are rather adhoc in nature, we formally prove the security of our scheme. Additionally, we show that obfuscated formulas are within a polynomial factor of the original ones thus achieving polynomial slowdown. Finally, the whole process is efficient in practice, allowing solutions to original instances to be easily recovered from obfuscated ones. A byproduct of our method is that all NP problems can be potentially outsourced to the cloud by means of reducing to SAT.
Last updated:  2023-10-21
Revisiting Meet-in-the-Middle Cryptanalysis of SIDH/SIKE with Application to the $IKEp182 Challenge
Aleksei Udovenko and Giuseppe Vitto
This work focuses on concrete cryptanalysis of the isogeny-based cryptosystems SIDH/SIKE under realistic memory/storage constraints. More precisely, we are solving the problem of finding an isogeny of a given smooth degree between two given supersingular elliptic curves. Recent works by Adj et al. (SAC 2018), Costello et al. (PKC 2020), Longa et al. (CRYPTO 2021) suggest that parallel "memoryless" golden collision search by van Oorschot-Wiener (JoC 1999) is the best realistic approach for the problem. We show instead that the classic meet-in-the-middle attack is still competitive due to its very low computational overhead, at least on small parameters. As a concrete application, we apply the meet-in-the-middle attack with optimizations to the $IKEp182 challenge posed by Microsoft Research. The attack was executed on a cluster and required less than 10 core-years and 256TiB of high-performance network storage (GPFS). Different trade-offs allow execution of the attack with similar time complexity and reduced storage requirements of only about 70TiB.
Last updated:  2023-10-21
Efficient Multiplicative-to-Additive Function from Joye-Libert Cryptosystem and Its Application to Threshold ECDSA
Haiyang Xue, Man Ho Au, Mengling Liu, Kwan Yin Chan, Handong Cui, Xiang Xie, Tsz Hon Yuen, and Chengru Zhang
Threshold ECDSA receives interest lately due to its widespread adoption in blockchain applications. A common building block of all leading constructions involves a secure conversion of multiplicative shares into additive ones, which is called the multiplicative-to-additive (MtA) function. MtA dominates the overall complexity of all existing threshold ECDSA constructions. Specifically, $O(n^2)$ invocations of MtA are required in the case of $n$ active signers. Hence, improvement of MtA leads directly to significant improvements for all state-of-the-art threshold ECDSA schemes. In this paper, we design a novel MtA by revisiting the Joye-Libert (JL) cryptosystem. Specifically, we revisit JL encryption and propose a JL-based commitment, then give efficient zero-knowledge proofs for JL cryptosystem which are the first to have standard soundness. Our new MtA offers the best time-space complexity trade-off among all existing MtA constructions. It outperforms state-of-the-art constructions from Paillier by a factor of $1.85$ to $2$ in bandwidth and $1.2$ to $1.7$ in computation. It is $7\times$ faster than those based on Castagnos-Laguillaumie encryption only at the cost of $2\times$ more bandwidth. While our MtA is slower than OT-based constructions, it saves $18.7\times$ in bandwidth requirement. In addition, we also design a batch version of MtA to further reduce the amotised time and space cost by another $25$%.
Last updated:  2023-10-20
Oblivious issuance of proofs
Michele Orrù, Stefano Tessaro, Greg Zaverucha, and Chenzhi Zhu
We consider the problem of creating, or issuing, zero-knowledge proofs obliviously. In this setting, a prover interacts with a verifier to produce a proof, known only to the verifier. The resulting proof is transferable and can be verified non-interactively by anyone. Crucially, the actual proof cannot be linked back to the interaction that produced it. This notion generalizes common approaches to designing blind signatures, which can be seen as the special case of proving "knowledge of a signing key", and extends the seminal work of Camenisch and Stadler ('97). We propose a provably secure construction of oblivious proofs, focusing on discrete-logarithm representation equipped with AND-composition. We also give three applications of our framework. First, we give a publicly verifiable version of the classical Diffie-Hellman based Oblivious PRF. This yields new constructions of blind signatures and publicly verifiable anonymous tokens. Second, we show how to "upgrade" keyed-verification anonymous credentials (Chase et al., CCS'14) to also be concurrently secure blind signatures on the same set of attributes. Crucially, our upgrade maintains the performance and functionality of the credential in the keyed-verification setting, we only change issuance. We observe that the existing issuer proof that the credential is well-formed may be verified by anyone; creating it with our framework makes it a blind signature, adding public verifiability to the credential system. Finally, we provide a variation of the U-Prove credential system that is provably one-more unforgeable with concurrent issuance sessions. This constitutes a fix for the attack illustrated by Benhamouda et al. (EUROCRYPT'21). Beyond these example applications, as our results are quite general, we expect they may enable modular design of new primitives with concurrent security, a goal that has historically been challenging to achieve.
Last updated:  2023-10-20
Vector Commitments With Proofs of Smallness: Short Range Proofs and More
Benoit Libert
Vector commitment schemes are compressing commitments to vectors that make it possible to succinctly open a commitment for individual vector positions without revealing anything about other positions. We describe vector commitments enabling constant-size proofs that the committed vector is small (i.e., binary, ternary, or of small norm). As a special case, we obtain range proofs featuring the shortest proof length in the literature with only $3$ group elements per proof. As another application, we obtain short pairing-based NIZK arguments for lattice-related statements. In particular, we obtain short proofs (comprised of $3$ group elements) showing the validity of ring LWE ciphertexts and public keys. Our constructions are proven simulation-extractable in the algebraic group model and the random oracle model.
Last updated:  2023-10-20
DEFEND: Towards Verifiable Delay Functions from Endomorphism Rings
Knud Ahrens and Jens Zumbrägel
We present a verifiable delay function based on isogenies of supersingular elliptic curves, using Deuring correspondence and computation of endomorphism rings for the delay. For each input x a verifiable delay function has a unique output y and takes a predefined time to evaluate, even with parallel computing. Additionally, it generates a proof by which the output can efficiently be verified. In our approach the input is a path in the 2-isogeny graph and the output is the maximal order isomorphic to the endomorphism ring of the curve at the end of that path. This approach is presumably quantum-secure, does not require a trusted setup or special primes and the verification is independent from the delay. It works completely within the isogeny setting and the computation of the proof causes no overhead. The efficient sampling of challenges however remains an open problem.
Last updated:  2023-10-20
Breaking the $O(\sqrt n)$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party
Elette Boyle, Ran Cohen, and Aarushi Goel
Byzantine agreement (BA), the task of $n$ parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of a vast range of distributed protocols. Interestingly, in protocols with the best overall communication, the demands of the parties are highly unbalanced: the amortized cost is $\tilde O(1)$ bits per party, but some parties must send $\Omega(n)$ bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $\tilde O(\sqrt{n})$. In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party communicates only $\tilde O(1)$ bits? Our contributions in this line are as follows: 1) We define a cryptographic primitive---succinctly reconstructed distributed signatures (SRDS)---that suffices for constructing $\tilde O(1)$ balanced BA. We provide two constructions of SRDS from different cryptographic and Public-Key Infrastructure (PKI) assumptions. 2) The SRDS-based BA follows a paradigm of boosting from "almost-everywhere" agreement to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends $o(n)$ messages. 3) We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product). Our results provide new approaches forward, as well as limitations and barriers, towards minimizing per-party communication of BA. In particular, we construct the first two BA protocols with $\tilde O(1)$ balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).
Last updated:  2023-10-20
One-time and Revocable Ring Signature with Logarithmic Size in Blockchain
Yang Li, Wei Wang, Dawei Zhang, and Xu Han
Ring signature (RS) allows users to demonstrate to verifiers their membership within a specified group (ring) without disclosing their identities. Based on this, RS can be used as a privacy protection technology for users' identities in blockchain. However, there is currently a lack of RS schemes that are fully applicable to the blockchain applications: Firstly, users can only spend a UTXO once, and the current RS schemes are not yet perfect in a one-time manner. At the same time, the current RS schemes are not sufficiently developed in terms of regulation. Secondly, the size of the current RS is mostly linearly related to the number of ring members. When there are many members, the transaction processing speed is slow. We propose a one-time and revocable ring signature with logarithmic size in blockchain based on the Sigma-Protocols. Our scheme compresses the RS size and enables users to sign in the blockchain transactions. The scheme allows two RS generated with the same private key for a same UTXO to be linked together. Additionally, it allows regulatory authority to recover the signer's identity at any time. A security model was presented, and its security properties, namely, unforgeability, anonymity, one-time, revocability, and non-slanderability were proven in the random oracle model. Our scheme compresses the RS size to where is the number of ring users, enabling blockchain transactions to have better processing speeds. And it can prevent double-spending attacks in blockchain and allows regulatory authority to recover the identity of the signer.
Last updated:  2023-10-20
On Decompositions of Permutations in Quadratic Functions
Samuele Andreoli, Enrico Piccione, Lilya Budaghyan, Pantelimon Stănică, and Svetla Nikova
The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation. Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over $\mathbb{F}_{2^n}$. We prove the existence of decompositions using quadratic and linear power permutations for all permutations when $2^n-1$ is a prime, and we prove the non-existence of such decompositions for power permutations of differential uniformity strictly lower than $16$ when $4|n$. We also prove that any permutation admits a decomposition into quadratic power permutations and affine permutations of the form $ax+b$ if $4 \nmid n$. Furthermore, we prove that any permutation admits a decomposition into cubic power permutations and affine permutations. Finally, we present a decomposition of the PRESENT S-Box using the power permutation $x^7$ and affine permutations.
Last updated:  2023-10-20
Patient Zero and Patient Six: Zero-Value and Correlation Attacks on CSIDH and SIKE
Fabio Campos, Michael Meyer, Krijn Reijnders, and Marc Stöttinger
Recent works have started side-channel analysis on SIKE and show the vulnerability of isogeny-based systems to zero-value attacks. In this work, we expand on such attacks by analyzing the behavior of the zero curve $E_0$ and six curve $E_6$ in CSIDH and SIKE. We demonstrate an attack on static-key CSIDH and SIKE implementations that recovers bits of the secret key by observing via zero-value-based resp. exploiting correlation-collision-based side-channel analysis whether secret isogeny walks pass over the zero or six curve. We apply this attack to fully recover secret keys of SIKE and two state-of-the-art CSIDH-based implementations: CTIDH and SQALE. We show the feasibility of exploiting side-channel information for the proposed attacks based on simulations with various realistic noise levels. Additionally, we discuss countermeasures to prevent zero-value and correlation-collision attacks against CSIDH and SIKE in our attacker model.
Last updated:  2023-10-20
HAETAE: Shorter Lattice-Based Fiat-Shamir Signatures
Jung Hee Cheon, Hyeongmin Choe, Julien Devevey, Tim Güneysu, Dongyeon Hong, Markus Krausz, Georg Land, Marc Möller, Damien Stehlé, and MinJune Yi
We present HAETAE (Hyperball bimodAl modulE rejecTion signAture schemE), a new lattice-based signature scheme. Like the NIST-selected Dilithium signature scheme, HAETAE is based on the Fiat-Shamir with Aborts paradigm, but our design choices target an improved complexity/compactness compromise that is highly relevant for many space-limited application scenarios. We primarily focus on reducing signature and verification key sizes so that signatures fit into one TCP or UDP datagram while preserving a high level of security against a variety of attacks. As a result, our scheme has signature and verification key sizes up to 39% and 25% smaller, respectively, compared than Dilithium. We provide a portable, constant-time reference implementation together with an optimized implementation using AVX2 instructions and an implementation with reduced stack size for the Cortex-M4. Moreover, we describe how to efficiently protect HAETAE against implementation attacks such as side-channel analysis, making it an attractive candidate for use in IoT and other embedded systems.
Last updated:  2023-10-20
MuSig2: Simple Two-Round Schnorr Multi-Signatures
Jonas Nick, Tim Ruffing, and Yannick Seurin
Multi-signatures enable a group of signers to produce a joint signature on a joint message. Recently, Drijvers et al. (S&P'19) showed that all thus far proposed two-round multi-signature schemes in the pure DL setting (without pairings) are insecure under concurrent signing sessions. While Drijvers et al. proposed a secure two-round scheme, this efficiency in terms of rounds comes with the price of having signatures that are more than twice as large as Schnorr signatures, which are becoming popular in cryptographic systems due to their practicality (e.g., they will likely be adopted in Bitcoin). If one needs a multi-signature scheme that can be used as a drop-in replacement for Schnorr signatures, then one is forced to resort either to a three-round scheme or to sequential signing sessions, both of which are undesirable options in practice. In this work, we propose MuSig2, a simple and highly practical two-round multi-signature scheme. This is the first scheme that simultaneously i) is secure under concurrent signing sessions, ii) supports key aggregation, iii) outputs ordinary Schnorr signatures, iv) needs only two communication rounds, and v) has similar signer complexity as ordinary Schnorr signatures. Furthermore, it is the first multi-signature scheme in the pure DL setting that supports preprocessing of all but one rounds, effectively enabling a non-interactive signing process without forgoing security under concurrent sessions. We prove the security of MuSig2 in the random oracle model, and the security of a more efficient variant in the combination of the random oracle and the algebraic group model. Both our proofs rely on a weaker variant of the OMDL assumption.
Last updated:  2023-10-20
A Note on ``A Time-Sensitive Token-Based Anonymous Authentication and Dynamic Group Key Agreement Scheme for Industry 5.0''
Zhengjun Cao and Lihua Liu
We show that the Xu et al.'s authentication and key agreement scheme [IEEE Trans. Ind. Informatics, 18(10), 7118-7127, 2022] is flawed. (1) It confused some operations for bilinear maps and presented some inconsistent computations. (2) It failed to keep anonymity, not as claimed. The adversary can use any device's public key stored in the blockchain to test some verification equations so as to reveal the identity of a target device.
Last updated:  2023-10-20
SPA-GPT: General Pulse Tailor for Simple Power Analysis Based on Reinforcement Learning
Ziyu Wang, Yaoling Ding, An Wang, Yuwei Zhang, Congming Wei, Shaofei Sun, and Liehuang Zhu
Power analysis of public-key algorithms is a well-known approach in the community of side-channel analysis. We usually classify operations based on the differences in power traces produced by different basic operations (such as modular exponentiation) to recover secret information like private keys. The more accurate the segmentation of power traces, the higher the efficiency of their classification. There exist two commonly used methods: one is equidistant segmentation, which requires a fixed number of basic operations and similar trace lengths for each type of operation, leading to limited application scenarios; the other is peak-based segmentation, which relies on personal experience to configure parameters, resulting in insufficient flexibility and poor universality. In this paper, we propose an automated power trace segmentation method based on reinforcement learning algorithms, which is applicable to a wide range of common implementation of public-key algorithms. Reinforcement learning is an unsupervised machine learning technique that eliminates the need for manual label collection. For the first time, this technique is introduced into the field of side-channel analysis for power trace processing. By using prioritized experience replay optimized Deep Q-Network algorithm, we reduce the number of parameters required to achieve accurate segmentation of power traces to only one, i.e. the key length. We also employ various techniques to improve the segmentation effectiveness, such as clustering algorithm, enveloped-based feature enhancement and fine-tuning method. We validate the effectiveness of the new method in nine scenarios involving hardware and software implementations of different public-key algorithms executed on diverse platforms such as microcontrollers, SAKURA-G, and smart cards. Specifically, one of these implementations is protected by time randomization countermeasures. Experimental results show that our method has good robustness on the traces with varying segment lengths and differing peak heights. After employ the clustering algorithm, our method achieves an accuracy of over 99.6% in operations recovery. Besides, power traces collected from these devices have been uploaded as databases, which are available for researchers engaged in public-key algorithms to conduct related experiments or verify our method.
Last updated:  2023-10-19
Improved SNARK Frontend for Highly Repetitive Computations
Sriram Sridhar and Yinuo Zhang
Modern SNARK designs usually feature a frontend-backend paradigm: The frontend compiles a user's program into some equivalent circuit representation, while the backend calls for a SNARK specifically made for proving circuit satisfiability. While the circuit may be defined over small fields, the backend prover often needs to lift the computation to much larger fields for achieving soundness. This gap results in concrete overheads, for example, when proving SHA2 programs with pairing-based SNARKs. For a class of computations that are \emph{highly repetitive}, we propose an improved frontend that partially bridges this gap. Compared with existing works, our frontend yields circuit representations defined over larger fields but of smaller size. Our implementation shows that for $\approx 100$ iterations of SHA2-256 instances, our improved frontend boosts prover runtime by over $3.8 \times$. Central to our result and of independent interest, is an efficient technique for proving non-native ring arithmetic.
Last updated:  2023-10-19
Defeating Low-Cost Countermeasures against Side-Channel Attacks in Lattice-based Encryption - A Case Study on Crystals-Kyber
Prasanna Ravi, Thales Paiva, Dirmanto Jap, Jan-Pieter D'Anvers, and Shivam Bhasin
In an effort to circumvent the high cost of standard countermeasures against side-channel attacks in post-quantum cryptography, some works have developed low-cost detection-based countermeasures. These countermeasures try to detect maliciously generated input ciphertexts and react to them by discarding the ciphertext or secret key. In this work, we take a look at two previously proposed low-cost countermeasures: the ciphertext sanity check and the decapsulation failure check, and demonstrate successful attacks on these schemes. We show that the first countermeasure can be broken with little to no overhead, while the second countermeasure requires a more elaborate attack strategy that relies on valid chosen ciphertexts. Thus, in this work, we propose the first chosen-ciphertext based side-channel attack that only relies on valid ciphertexts for key recovery. As part of this attack, a third contribution of our paper is an improved solver that retrieves the secret key from linear inequalities constructed using side-channel leakage from the decryption procedure. Our solver is an improvement over the state-of-the-art Belief Propagation solvers by Pessl and Prokop, and later Delvaux. Our method is simpler, easier to understand and has lower computational complexity, while needing less than half the inequalities compared to previous methods.
Last updated:  2023-10-19
Et tu, Brute? SCA Assisted CCA using Valid Ciphertexts - A Case Study on HQC KEM
Thales Paiva, Prasanna Ravi, Dirmanto Jap, and Shivam Bhasin
HQC is a code-based key encapsulation mechanism (KEM) that was selected to move to the fourth round of the NIST post-quantum standardization process. While this scheme was previously targeted by side-channel assisted chosen-ciphertext attacks for key recovery, we notice that all of these attacks use malformed ciphertexts, which can be easily detected since they cause a decapsulation failure. In this case, designers may chose as a countermeasure to refresh the key whenever a failure occurs, making these previous attacks ineffective. In this work, we present the first side-channel assisted chosen-ciphertext attacks using valid ciphertexts which can be carried out in a stealthy manner for key recovery. Our attacks target side-channel leakage from two different operations within the Reed-Muller decoder used for decryption, and can recover the secret key with 100% success rate, even in the presence of errors in side-channel information. All our experiments are performed on the open-source implementation of HQC KEM taken from the pqm4 library, with our attacks validated using both the power and EM side-channel. We also demonstrate novel key recovery attacks which also work on shuffled implementations, and discuss applicability of our attack to masking countermeasures. To the best of our knowledge, we are not aware of a side-channel protected design for HQC KEM, and thus we believe our work stresses the need towards more research on secure and efficient masking and hiding countermeasures for HQC KEM.
Last updated:  2023-10-19
Sigmabus: Binding Sigmas in Circuits for Fast Curve Operations
George Kadianakis, Mary Maller, and Andrija Novakovic
This paper introduces Sigmabus, a technique designed to enhance the efficiency of zero-knowledge circuits by relocating computationally expensive operations outside the circuit. Specifically, Sigmabus focuses on moving elliptic curve group operations, typically proven with expensive non-native field arithmetic, to external computations. By leveraging Sigma protocols, elliptic curve group operations are proven outside the circuit, while additional constraints are applied to the circuit to ensure correct execution of the Sigma protocol. This approach can achieve significant performance improvements in zero-knowledge circuits. This paper presents the Sigmabus protocol along with its security proofs, and demonstrates its practical implications through various use cases.
Last updated:  2023-10-19
On the (Not So) Surprising Impact of Multi-Path Payments on Performance and Privacy in the Lightning Network
Charmaine Ndolo and Florian Tschorsch
The Lightning network (LN) addresses Bitcoin’s scalability issues by providing fast and private payment processing. In order to mitigate failures caused by insufficient channel capacities, LN introduced multi-path payments. To the best of our knowledge, the effect of multi-path payments remains unclear. In this paper, we therefore study the impact of multi-path payments on performance and privacy. We identify metrics quantifying the aforementioned properties and utilise them to evaluate the impact of multi-path payments. To this end, we develop a simulator implementing pathfinding in LN using single and multi-path payments as well as various pathfinding algorithms. We find that, while the success rate of multi-path payments is up to 20% higher, the impact of multi-path payments on performance otherwise remains within limits. On the other hand, the impact on privacy appears to be greater, e.g., multi-path payments are more likely to encounter an on-path adversary and the relationship anonymity is more likely to be compromised by colluding intermediate hops. However, multi-path payments are less likely to be deanonymised based on the path lengths.
Last updated:  2023-10-19
Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large Spaces
Dario Fiore, Dimitris Kolonelos, and Paola de Perthuis
Registration-Based Encryption (RBE) [Garg et al. TCC'18] is a public-key encryption mechanism in which users generate their own public and secret keys, and register their public keys with a central authority called the key curator. Similarly to Identity-Based Encryption (IBE), in RBE users can encrypt by only knowing the public parameters and the public identity of the recipient. Unlike IBE, though, RBE does not suffer the key escrow problem — one of the main obstacles of IBE's adoption in practice — since the key curator holds no secret. In this work, we put forward a new methodology to construct RBE schemes that support large users identities (i.e., arbitrary strings). Our main result is the first efficient pairing-based RBE for large identities. Prior to our work, the most efficient RBE is that of [Glaeser et al. ePrint'22] which only supports small identities. The only known RBE schemes with large identities are realized either through expensive non-black-box techniques (ciphertexts of 3.6 TB for 1000 users), or via a specialized lattice-based construction [Döttling et al. Eurocrypt'23] (ciphertexts of 2.4 GB), or through the more complex notion of Registered Attribute-Based Encryption [Hohenberger et al. Eurocrypt’23]. By unlocking the use of pairings for RBE with large identity space, we enable a further improvement of three orders of magnitude, as our ciphertexts for a system with 1000 users are 1.7 MB. The core technique of our approach is a novel use of cuckoo hashing in cryptography that can be of independent interest. We give two main applications. The first one is the aforementioned RBE methodology, where we use cuckoo hashing to compile an RBE with small identities into one for large identities. The second one is a way to convert any vector commitment scheme into a key-value map commitment. For instance, this leads to the first algebraic pairing-based key-value map commitments.
Last updated:  2023-10-19
Ring Verifiable Random Functions and Zero-Knowledge Continuations
Jeffrey Burdges, Oana Ciobotaru, Handan Kılınç Alper, Alistair Stewart, and Sergey Vasilyev
We introduce a new cryptographic primitive, named ring verifiable random function (ring VRF). Ring VRF combines properties of VRF and ring signatures, offering verifiable unique, pseudorandom outputs while ensuring anonymity of the output and message authentication. We design its security in the universal composability (UC) framework and construct two protocols secure in our model. We also formalize a new notion of zero-knowledge (ZK) continuations allowing for the reusability of proofs by randomizing and enhancing the efficiency of one of our ring VRF schemes. We instantiate this notion with our protocol SpecialG which allows a prover to reprove a statement in a constant time and be unlikable to the previous proof(s).
Last updated:  2023-10-19
Concrete Analysis of Quantum Lattice Enumeration
Shi Bai, Maya-Iggy van Hoof, Floyd B. Johnson, Tanja Lange, and Tran Ngo
Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some ``enumeration tree'' whose nodes denote a partial assignment of the coefficients, corresponding to lattice points as a linear combination of the lattice basis with the coefficients. This work provides a concrete analysis for the cost of quantum lattice enumeration based on Montanaro's quantum tree backtracking algorithm. More precisely, we give a concrete implementation in the quantum circuit model. We also show how to optimize the circuit depth by parallelizing the components. Based on the circuit designed, we discuss the concrete quantum resource estimates required for lattice enumeration.
Last updated:  2023-10-19
STAMP-Single Trace Attack on M-LWE Pointwise Multiplication in Kyber
Bolin Yang, Prasanna Ravi, Fan Zhang, Ao Shen, and Shivam Bhasin
In this work, we propose a novel single-trace key recovery attack targeting side-channel leakage from the key-generation and encryption procedure of Kyber KEM. Our attack exploits the inherent nature of the Module-Learning With Errors (Module-LWE) problem used in Kyber KEM. We demonstrate that the inherent reliance of Kyber KEM on the Module-LWE problem results in higher number of repeated and secret key-related computations, referred to as STAMPs appearing on a single side channel trace, compared to the Ring-LWE problem of similar security level. We exploit leakage from the pointwise multiplication operation and take advantage of the properties of the Module-LWE instance to enable a potential single trace key recovery attack. We validated the efficacy of our attack on both simulated and real traces, and we performed experiments on both the reference and assembly optimized implementation of Kyber KEM, taken from the pqm4 library, a well-known benchmarking and testing framework for PQC schemes on the ARM Cortex-M4 microcontroller. We also analyze the applicability of our attack on countermeasures against traditional SCA such as masking and shuffling. We believe our work motivates more research towards SCA resistant implementation of key-generation and encryption procedure for Kyber KEM.
Last updated:  2023-10-18
Waffle: An Online Oblivious Datastore for Protecting Data Access Patterns
Sujaya Maiyya, Sharath Vemula, Divyakant Agrawal, Amr El Abbadi, and Florian Kerschbaum
We present Waffle, a datastore that protects an application’s data access patterns from a passive persistent adversary. Waffle achieves this without prior knowledge of the input data access distribution, making it the first of its kind to adaptively handle input sequences under a passive persistent adversary. Waffle maintains a constant bandwidth and client-side storage overhead, which can be adjusted to suit the application owner’s preferences. This flexibility allows the owner to fine-tune system parameters and strike a balance between security and performance. Our evaluation, utilizing the Yahoo! Cloud Serving Benchmark (YCSB) benchmark and Redis as the backend storage, demonstrates promising results. The insecure baseline outperforms Waffle by a mere 5-6x, whereas Waffle outperforms Pancake—a state-of-the-art oblivious datastore under passive persistent adversaries—by 45-57%, and a concurrent ORAM system, TaoStore, by 102x.
Last updated:  2023-10-18
Post-Quantum Security for the Extended Access Control Protocol
Marc Fischlin, Jonas von der Heyden, Marian Margraf, Frank Morgner, Andreas Wallner, and Holger Bock
The Extended Access Control (EAC) protocol for authenticated key agreement is mainly used to secure connections between machine-readable travel documents (MRTDs) and inspection terminals, but it can also be adopted as a universal solution for attribute-based access control with smart cards. The security of EAC is currently based on the Diffie-Hellman problem, which may not be hard when considering quantum computers. In this work we present PQ-EAC, a quantum-resistant version of the EAC protocol. We show how to achieve post-quantum confidentiality and authentication without sacrificing real-world usability on smart cards. To ease adoption, we present two main versions of PQ-EAC: One that uses signatures for authentication and one where authentication is facilitated using long-term KEM keys. Both versions can be adapted to achieve forward secrecy and to reduce round complexity. To ensure backwards-compatibility, PQ-EAC can be implemented using only Application Protocol Data Units (APDUs) specified for EAC in standard BSI TR-03110. Merely the protocol messages needed to achieve forward secrecy require an additional APDU not specified in TR-03110. We prove security of all versions in the real-or-random model of Bellare and Rogaway. To show real-world practicality of PQ-EAC we have implemented a version using signatures on an ARM SC300 security controller, which is typically deployed in MRTDs. We also implemented PQ-EAC on a VISOCORE terminal for border control. We then conducted several experiments to evaluate the performance of PQ-EAC executed between chip and terminal under various real-world conditions. Our results strongly suggest that PQ-EAC is efficient enough for use in border control.
Last updated:  2023-10-18
Designing Efficient and Flexible NTT Accelerators
Ahmet MALAL
The Number Theoretic Transform (NTT) is a powerful mathematical tool with a wide range of applications in various fields, including signal processing, cryptography, and error correction codes. In recent years, there has been a growing interest in efficiently implementing the NTT on hardware platforms for lattice-based cryptography within the context of NIST's Post-Quantum Cryptography (PQC) competition. The implementation of NTT in cryptography stands as a pivotal advancement, revolutionizing various security protocols. By enabling efficient arithmetic operations in polynomial rings, NTT significantly enhances the speed and security of lattice-based cryptographic schemes, contributing to the development of robust homomorphic encryption, key exchange, and digital signature systems. This article presents a new implementation of the Number Theoretic Transform for FPGA platforms. The focus of the implementation lies in achieving a flexible trade-off between resource usage and computation speed. By strategically adjusting the allocation of BRAM and DSP resources, the NTT computation can be optimized for either high-speed processing or resource conservation. The proposed implementation is specifically designed for polynomial multiplication with a degree of 256, accommodating coefficients of various bit sizes. Furthermore, the constant-geometry (Pease) method was utilized as an alternative to the Cooley-Tukey graph method, resulting in a notable simplification of BRAM addressing procedures. This adaptability renders it suitable for cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber, which use 256-degree polynomials.
Last updated:  2023-10-18
On the Impossibility of Surviving (Iterated) Deletion of Weakly Dominated Strategies in Rational MPC
Johannes Blömer, Jan Bobolz, and Henrik Bröcher
Rational multiparty computation (rational MPC) provides a framework for analyzing MPC protocols through the lens of game theory. One way to judge whether an MPC protocol is rational is through weak domination: Rational players would not adhere to an MPC protocol if deviating never decreases their utility, but sometimes increases it. Secret reconstruction protocols are of particular importance in this setting because they represent the last phase of most (rational) MPC protocols. We show that most secret reconstruction protocols from the literature are not, in fact, stable with respect to weak domination. Furthermore, we formally prove that (under certain assumptions) it is impossible to design a secret reconstruction protocol which is a Nash equlibrium but not weakly dominated if (1) shares are authenticated or (2) half of all players may form a coalition.
Last updated:  2023-10-18
DeVoS: Deniable Yet Verifiable Vote Updating
Johannes Mueller, Balazs Pejo, and Ivan Pryvalov
Internet voting systems are supposed to meet the same high standards as traditional paper-based systems when used in real political elections: freedom of choice, universal and equal suffrage, secrecy of the ballot, and independent verifiability of the election result. Although numerous Internet voting systems have been proposed to achieve these challenging goals simultaneously, few come close in reality. We propose a novel publicly verifiable and practically efficient Internet voting system, DeVoS, that advances the state of the art. The main feature of DeVoS is its ability to protect voters' freedom of choice in several dimensions. First, voters in DeVoS can intuitively update their votes in a way that is deniable to observers but verifiable by the voters; in this way voters can secretly overwrite potentially coerced votes. Second, in addition to (basic) vote privacy, DeVoS also guarantees strong participation privacy by end-to-end hiding which voters have submitted ballots and which have not. Finally, DeVoS is fully compatible with Perfectly Private Audit Trail, a state-of-the-art Internet voting protocol with practical everlasting privacy. In combination, DeVoS offers a new way to secure free Internet elections with strong and long-term privacy properties.
Last updated:  2023-10-18
Oracle Recording for Non-Uniform Random Oracles, and its Applications
Minki Hhan and Aaram Yun
In Crypto 2019, Zhandry showed how to define compressed oracles, which record quantum superposition queries to the quantum random oracle. In this paper, we extend Zhandry's compressed oracle technique to non-uniformly distributed functions with independently sampled outputs. We define two quantum oracles $\mathsf{CStO}_D$ and $\mathsf{CPhsO}_D$, which are indistinguishable to the non-uniform quantum random oracle where quantum access is given to a random function $H$ whose images $H(x)$ are sampled from a probability distribution $D$ independently for each $x$. We show that these compressed oracles record the adversarial quantum superposition queries. Also, we re-prove the optimality of Grover search and the collision resistance of non-uniform random functions, using our extended compressed oracle technique.
Last updated:  2023-10-18
A Methodology to Achieve Provable Side-Channel Security in Real-World Implementations
Uncategorized
Sonia Belaïd, Gaëtan Cassiers, Camille Mutschler, Matthieu Rivain, Thomas Roche, François-Xavier Standaert, and Abdul Rahman Taleb
Show abstract
Uncategorized
Physical side-channel attacks exploit a device's emanations to compromise the security of cryptographic implementations. Many countermeasures have been proposed against these attacks, especially the widely-used and efficient masking countermeasure. While theoretical models offer formal security proofs, they often rest on unrealistic assumptions, leading current approaches to prove the security of masked implementations to primarily rely on empirical verification. Consequently, the literature still lacks a well-defined framework for implementing proven secure constructions on physical devices. In this paper, we present a comprehensive methodology to transform an abstract circuit into a physical implementation secure against side-channel attacks. We introduce new tools for adapting the ideal noisy leakage model to practical scenarios. We also highlight the design objectives for embedded devices to achieve high levels of security, while acknowledging the limitations and challenges in applying leakage models in practice. Our aim is to demonstrate the possibility of bridging theory and practice, encouraging further research to achieve practical implementations proven secure against side-channel attacks without relying on ideal assumptions about the leakage.
Last updated:  2023-10-18
FPT: a Fixed-Point Accelerator for Torus Fully Homomorphic Encryption
Michiel Van Beirendonck, Jan-Pieter D'Anvers, Furkan Turan, and Ingrid Verbauwhede
Fully Homomorphic Encryption (FHE) 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 invoked after each encrypted logical/arithmetical operation. 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 that prefer floating-point or integer FFTs. FPT is built as a streaming processor inspired by traditional streaming DSPs: it instantiates directly cascaded high-throughput computational stages, with minimal 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. Our proposed approach allows 100% utilization of arithmetic units and requires only a small bootstrapping key cache, 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 is typically constrained by memory and bandwidth. FPT is fully implemented and evaluated as a bootstrapping FPGA kernel for an Alveo U280 datacenter accelerator card. FPT achieves two to 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:  2023-10-17
Mitigating MEV via Multiparty Delay Encryption
Amirhossein Khajehpour, Hanzaleh Akbarinodehi, Mohammad Jahanara, and Chen Feng
Ethereum is a decentralized and permissionless network offering several attractive features. However, block proposers in Ethereum can exploit the order of transactions to extract value. This phenomenon, known as maximal extractable value (MEV), not only disrupts the optimal functioning of different protocols but also undermines the stability of the underlying consensus mechanism. In this work, we present a new method to alleviate the MEV problem by separating transaction inclusion and execution, keeping transactions encrypted before execution. We formulate the notion of multiparty delay encryption (MDE) and construct a practical MDE scheme based on time-lock puzzles. Unlike other encryption-based methods, our method excels in scalability (in terms of transaction decryption), efficiency (minimizing communication and storage overhead), and security (with minimal trust assumptions). To demonstrate the effectiveness of our MDE scheme, we have implemented it on a local Ethereum testnet. We also prove that with the presence of just one honest attestation aggregator per slot, the MEV threat can be significantly mitigated in a practical way.
Last updated:  2023-10-17
Power circuits: a new arithmetization for GKR-styled sumcheck
Lev Soukhanov
Goldwasser-Kalai-Rothblum protocol (GKR) for layered circuits is a sumcheck-based argument of knowledge for layered circuits, running in $\sim 2\mu \ell$ amount of rounds, where $\ell$ is the amount of layers and $\mu$ is the average layer logsize. For a layer $i$ of size $2^{\mu_i}$ the main work consists of running a sumcheck protocol of the form \[\underset{x,y}{\sum} \text{Add}_i(x,y,z)(f(x)+f(y)) + \text{Mul}_i(x,y,z)f(x)f(y)\] over a $2^{2\mu_i}$-dimensional cube, where $\text{Add}_i(x,y,z)$ and $\text{Mul}_i(x,y,z)$ are (typically relatively sparse) polynomials called "wiring predicates". We present a different approach, based on the (trivial) observation that multiplication can be expressed through linear operations and squaring. This leads to the different wiring, which is marginally more efficient even in a worst-case scenario, and decreases the amount of communication $\sim 2 \times$ in the case where wiring predicates are sparse.
Last updated:  2023-10-17
An Efficient ZK Compiler from SIMD Circuits to General Circuits
Dung Bui, Haotian Chu, Geoffroy Couteau, Xiao Wang, Chenkai Weng, Kang Yang, and Yu Yu
We propose a generic compiler that can convert any zero-knowledge proof for SIMD circuits to general circuits efficiently, and an extension that can preserve the space complexity of the proof systems. Our compiler can immediately produce new results improving upon state of the art. -By plugging in our compiler to Antman, an interactive sublinear-communication protocol, we improve the overall communication complexity for generalcircuits from $\mathcal{O}(C^{3/4})$ to $\mathcal{O}(C^{1/2})$. Our implementation shows that for a circuit of size $2^{27}$, it achieves up to $83.6\times$ improvement on communication compared to the state-of-the-art implementation. Its end-to-end running time is at least $70\%$ faster in a $10$Mbps network. -Using recent results on compressed $\Sigma$-protocol theory, we obtain a discrete-log-based constant-round zero-knowledge argument with $\mathcal{O}(C^{1/2})$ communication and common random string length, improving over the state of the art that has linear-size common random string and requires heavier computation. -We improve the communication of a designated $n$-verifier zero-knowledge proof from $\mathcal{O}(nC/B+n^2B^2)$ to $\mathcal{O}(nC/B+n^2)$. To demonstrate the scalability of our compilers, we were able to extract a commit-and-prove SIMD ZK from Ligero and cast it in our framework. We also give one instantiation derived from LegoSNARK, demonstrating that the idea of CP-SNARK also fits in our methodology.
Last updated:  2023-10-17
Rotatable Zero Knowledge Sets: Post Compromise Secure Auditable Dictionaries with application to Key Transparency
Brian Chen, Yevgeniy Dodis, Esha Ghosh, Eli Goldin, Balachandar Kesavan, Antonio Marcedone, and Merry Ember Mou
Key Transparency (KT) systems allow end-to-end encrypted service providers (messaging, calls, etc.) to maintain an auditable directory of their users’ public keys, producing proofs that all participants have a consistent view of those keys, and allowing each user to check updates to their own keys. KT has lately received a lot of attention, in particular its privacy preserving variants, which also ensure that users and auditors do not learn anything beyond what is necessary to use the service and keep the service provider accountable. Abstractly, the problem of building such systems reduces to constructing so-called append-only Zero-Knowledge Sets (aZKS). Unfortunately, existing aZKS (and KT) solutions do not allow to adequately restore the privacy guarantees after a server compromise, a form of Post-Compromise Security (PCS), while maintaining the auditability properties. In this work we address this concern through the formalization of an extension of aZKS called Rotatable ZKS (RZKS). In addition to providing PCS, our notion of RZKS has several other attractive features, such as a stronger (extractable) soundness notion, and the ability for a communication party with out-of-date data to efficiently “catch up” to the current epoch while ensuring that the server did not erase any of the past data. Of independent interest, we also introduce a new primitive called a Rotatable Verifiable Random Function (VRF), and show how to build RZKS in a modular fashion from a rotatable VRF, ordered accumulator, and append-only vector commitment schemes.
Last updated:  2023-10-17
StaTI: Protecting against Fault Attacks Using Stable Threshold Implementations
Siemen Dhooghe, Artemii Ovchinnikov, and Dilara Toprakhisar
Fault attacks impose a serious threat against the practical implementations of cryptographic algorithms. Statistical Ineffective Fault Attacks (SIFA), exploiting the dependency between the secret data and the fault propagation overcame many of the known countermeasures. Later, several countermeasures have been proposed to tackle this attack using error detection methods. However, the efficiency of the countermeasures, in part governed by the number of error checks, still remains a challenge. In this work, we propose a fault countermeasure, StaTI, based on threshold implementations and linear encoding techniques. The proposed countermeasure protects the implementations of cryptographic algorithms against both side-channel and fault adversaries in a non-combined attack setting. We present a new composable notion, stability, to protect a threshold implementation against a formal gate/register-faulting adversary. Stability ensures fault propagation, making a single error check of the output suffice. To illustrate the stability notion, first, we provide stable encodings of the XOR and AND gates. Then, we present techniques to encode threshold implementations of S-boxes, and provide stable encodings of some quadratic S-boxes together with their security and performance evaluation. Additionally, we propose general encoding techniques to transform a threshold implementation of any function (e.g., non-injective functions) to a stable one. We then provide an encoding technique to use in symmetric primitives which encodes state elements together significantly reducing the encoded state size. Finally, we used StaTI to implement a secure Keccak on FPGA and report on its efficiency.
Last updated:  2023-10-17
Can Alice and Bob Guarantee Output to Carol?
Bar Alon, Eran Omri, and Muthuramakrishnan Venkitasubramaniam
In the setting of solitary output computations, only a single designated party learns the output of some function applied to the private inputs of all participating parties with the guarantee that nothing beyond the output is revealed. The setting of solitary output functionalities is a special case of secure multiparty computation, which allows a set of mutually distrusting parties to compute some function of their private inputs. The computation should guarantee some security properties, such as correctness, privacy, fairness, and output delivery. Full security captures all these properties together. Solitary output computation is a common setting that has become increasingly important, as it is relevant to many real-world scenarios, such as federated learning and set disjointness. In the set-disjointness problem, a set of parties with private datasets wish to convey to another party whether they have a common input. In this work, we investigate the limits of achieving set-disjointness which already has numerous applications and whose feasibility (under non-trivial conditions) was left open in the work of Halevi et al. (TCC 2019). Towards resolving this, we completely characterize the set of Boolean functions that can be computed in the three-party setting in the face of a malicious adversary that corrupts up to two of the parties. As a corollary, we characterize the family of set-disjointness functions that can be computed in this setting, providing somewhat surprising results regarding this family and resolving the open question posed by Halevi et al.
Last updated:  2023-10-17
On Circuit Private, Multikey and Threshold Approximate Homomorphic Encryption
Kamil Kluczniak and Giacomo Santato
Homomorphic encryption for approximate arithmetic allows one to encrypt discretized real/complex numbers and evaluate arithmetic circuits over them. The first scheme, called CKKS, was introduced by Cheon et al. (Asiacrypt 2017) and gained tremendous attention. The enthusiasm for CKKS-type encryption stems from its potential to be used in inference or multiparty computation tasks that do not require an exact output. A desirable property for homomorphic encryption is circuit privacy, which requires that a ciphertext leaks no information on the computation performed to obtain it. Despite numerous improvements directed toward improving efficiency, the question of circuit privacy for approximate homomorphic encryption remains open. In this paper, we give the first formal study of circuit privacy for homomorphic encryption over approximate arithmetic. We introduce formal models that allow us to reason about circuit privacy. Then, we show that approximate homomorphic encryption can be made circuit private using tools from differential privacy with appropriately chosen parameters. In particular, we show that by applying an exponential (in the security parameter) Gaussian noise on the evaluated ciphertext, we remove useful information on the circuit from the ciphertext. Crucially, we show that the noise parameter is tight, and taking a lower one leads to an efficient adversary against such a system. We expand our definitions and analysis to the case of multikey and threshold homomorphic encryption for approximate arithmetic. Such schemes allow users to evaluate a function on their combined inputs and learn the output without leaking anything on the inputs. A special case of multikey and threshold encryption schemes defines a so-called partial decryption algorithm where each user publishes a ``masked'' version of its secret key, allowing all users to decrypt a ciphertext. Similarly, in this case, we show that applying a proper differentially private mechanism gives us IND-CPA-style security where the adversary additionally gets as input the partial decryptions. This is the first security analysis of approximate homomorphic encryption schemes that consider the knowledge of partial decryptions. As part of our study, we scrutinize recent proposals for the definition and constructions of threshold homomorphic encryption schemes and show new random oracle uninstantiability results that may be of independent interest.
Last updated:  2023-10-17
Efficient Lattice-based Sublinear Arguments for R1CS without Aborts
Intak Hwang, Jinyeong Seo, and Yongsoo Song
We propose a new lattice-based sublinear argument for R1CS that not only achieves efficiency in concrete proof size but also demonstrates practical performance in both proof generation and verification. To reduce the proof size, we employ a new encoding method for large prime fields, resulting in a compact proof for R1CS over such fields. We also devise a new proof technique that randomizes the input message. This results in fast proof generation performance, eliminating rejection sampling from the proving procedure. Compared to Ligero (CCS 2017), a hash-based post-quantum SNARK, our proof system yields a comparable proof size and proof generation performance, and excels in verification performance by an order of magnitude.
Last updated:  2023-10-17
Three Party Secure Computation with Friends and Foes
Bar Alon, Amos Beimel, and Eran Omri
In secure multiparty computation (MPC), the goal is to allow a set of mutually distrustful parties to compute some function of their private inputs in a way that preserves security properties, even in the face of adversarial behavior by some of the parties. However, classical security definitions do not pose any privacy restrictions on the view of honest parties. Thus, if an attacker adversarially leaks private information to honest parties, it does not count as a violation of privacy. This is arguably undesirable, and in real-life scenarios, it is hard to imagine that possible users would agree to have their private information revealed, even if only to other honest parties. To address this issue, Alon et al. [CRYPTO 20] introduced the notion of security with friends and foes (FaF security). In essence, $(t,h)$-FaF security requires that a malicious adversary corrupting up to $t$ parties cannot help a coalition of $h$ semi-honest parties to learn anything beyond what they can learn from their inputs and outputs (combined with the input and outputs of the malicious parties). They further showed that $(t,h)$-FaF security with $n$ parties is achievable for any functionality if $2t+h<n$, and for some functionality, $(t,h)$-FaF security is impossible assuming $2t+h\geq n$. A remaining important open problem is to characterize the set of $n$-party functionalities that can be computed with $(t,h)$-FaF security assuming $2t+h\geq n$. In this paper, we focus on the special, yet already challenging, case of $(1,1)$-FaF security for three-party, 2-ary (two inputs), symmetric (all parties output the same value) functionalities. We provide several positive results, a lower bound on the round complexity, and an impossibility result. In particular, we prove the following. (1) we identify a large class of three-party Boolean symmetric 2-ary functionalities that can be computed with $(1,1)$-FaF full security, and (2) We identify a large class of three-party (possibly non-Boolean) symmetric 2-ary functionalities, for which no $O(\log\kappa)$-round protocol computes them with $(1,1)$-FaF full security. This matches the round complexity of our positive results for various interesting functionalities, such as equality of strings.
Last updated:  2023-10-17
The Pre-Shared Key Modes of HPKE
Joël Alwen, Jonas Janneck, Eike Kiltz, and Benjamin Lipp
The Hybrid Public Key Encryption (HPKE) standard was recently published as RFC 9180 by the Crypto Forum Research Group (CFRG) of the Internet Research Task Force (IRTF). The RFC specifies an efficient public key encryption scheme, combining asymmetric and symmetric cryptographic building blocks. Out of HPKE’s four modes, two have already been formally analyzed by Alwen et al. (EUROCRYPT 2021). This work considers the remaining two modes: HPKE_PSK and HPKE_AuthPSK . Both of them are “pre-shared key” modes that assume the sender and receiver hold a symmetric pre-shared key. We capture the schemes with two new primitives which we call pre-shared key public-key encryption (pskPKE) and pre-shared key authenticated public-key encryption (pskAPKE). We provide formal security models for pskPKE and pskAPKE and prove (via general composition theorems) that the two modes HPKE_PSK and HPKE_AuthPSK offer active security (in the sense of insider privacy and outsider authenticity) under the Gap Diffie-Hellman assumption. We furthermore explore possible post-quantum secure instantiations of the HPKE standard and propose new solutions based on lattices and isogenies. Moreover, we show how HPKE’s basic HPKEPSK and HPKEAuthPSK modes can be used black-box in a simple way to build actively secure post-quantum/classic-hybrid (authenticated) encryption schemes. Our hybrid constructions provide a cheap and easy path towards a practical post-quantum secure drop-in replacement for the basic HPKE modes HPKE_Base and HPKE_Auth .
Last updated:  2023-10-17
Noah's Ark: Efficient Threshold-FHE Using Noise Flooding
Morten Dahl, Daniel Demmler, Sarah El Kazdadi, Arthur Meyre, Jean-Baptiste Orfila, Dragos Rotaru, Nigel P. Smart, Samuel Tap, and Michael Walter
We outline a secure and efficient methodology to do threshold distributed decryption for LWE based Fully Homomorphic Encryption schemes. Due to the smaller parameters used in some FHE schemes, such as Torus-FHE (TFHE), the standard technique of ``noise flooding'' seems not to apply. We show that noise flooding can also be used with schemes with such small parameters, by utilizing a switch to a scheme with slightly higher parameters and then utilizing the efficient bootstrapping operations which TFHE offers. Our protocol is proved secure via a simulation argument, making its integration in bigger protocols easier to manage.
Last updated:  2023-10-17
Formal Analysis of Non-profiled Deep-learning Based Side-channel Attacks
Akira Ito, Rei Ueno, Rikuma Tanaka, and Naofumi Homma
This paper formally analyzes two major non-profiled deep-learning-based side-channel attacks (DL-SCAs): differential deep-learning analysis (DDLA) by Timon and collision DL-SCA by Staib and Moradi. These DL-SCAs leverage supervised learning in non-profiled scenarios. Although some intuitive descriptions of these DL-SCAs exist, their formal analyses have been rarely conducted yet, which makes it unclear why and when the attacks succeed and how the attack can be improved. In this paper, we provide the first information-theoretical analysis of DDLA. We reveal its relevance to the mutual information analysis (MIA), and then present three theorems stating some limitations and impossibility results of DDLA. Subsequently, we provide the first probability-theoretical analysis on collision DL-SCA. After presenting its formalization with a proposal of our distinguisher for collision DL-SCA, we prove its optimality. Namely, we prove that the collision DL-SCA using our distinguisher theoretically maximizes the success rate if the neural network (NN) training is completely successful (namely, the NN completely imitates the true conditional probability distribution). Accordingly, we propose an improvement of the collision DL-SCA based on a dedicated NN architecture and a full-key recovery methodology using multiple neural distinguishers. Finally, we experimentally evaluate non-profiled (DL-)SCAs using a newly created dataset using publicly available first-order masked AES implementation. The existing public dataset of side-channel traces is insufficient to evaluate collision DL-SCAs due to a lack of substantive side-channel traces for different key values. Our dataset enables a comprehensive evaluation of collision (DL-)SCAs, which clarifies the current situation of non-profiled (DL-)SCAs.
Last updated:  2023-10-17
Manifold Learning Side-Channel Attacks against Masked Cryptographic Implementations
Jianye Gao, Xinyao Li, Changhai Ou, Zhu Wang, and Fei Yan
Masking, as a common countermeasure, has been widely utilized to protect cryptographic implementations against power side-channel attacks. It significantly enhances the difficulty of attacks, as the sensitive intermediate values are randomly partitioned into multiple parts and executed on different times. The adversary must amalgamate information across diverse time samples before launching an attack, which is generally accomplished by feature extraction (e.g., Points-Of-Interest (POIs) combination and dimensionality reduction). However, traditional POIs combination methods, machine learning and deep learning techniques are often too time consuming, and necessitate a significant amount of computational resources. In this paper, we undertake the first study on manifold learning and their applications against masked cryptographic implementations. The leaked information, which manifests as the manifold of high-dimensional power traces, is mapped into a low-dimensional space and achieves feature extraction through manifold learning techniques like ISOMAP, Locally Linear Embedding (LLE), and Laplacian Eigenmaps (LE). Moreover, to reduce the complexity, we further construct explicit polynomial mappings for manifold learning to facilitate the dimensionality reduction. Compared to the classical machine learning and deep learning techniques, our schemes built from manifold learning techniques are faster, unsupervised, and only require very simple parameter tuning. Their effectiveness has been fully validated by our detailed experiments.
Last updated:  2023-10-16
Breaking Parallel ROS: Implication for Isogeny and Lattice-based Blind Signatures
Shuichi Katsumata, Yi-Fu Lai, and Michael Reichle
Many of the three-round blind signatures based on identification protocols are only proven to be $\ell$-concurrently unforgeable for $\ell = \mathsf{polylog}(\lambda)$. It was only recently shown in a seminal work by Benhamouda et al. (EUROCRYPT'21) that this is not just a limitation of the proof technique. They proposed an elegant polynomial time attack against the $\ell$-concurrently unforgeability of the classical blind Schnorr protocol for $\ell = \mathsf{poly}(\lambda)$. However, there are still many blind signatures following a similar recipe to blind Schnorr where the attack by Benhamouda et al. does not apply. This includes for instance the isogeny-based blind signature CSI-Otter by Katsumata et al (CRYPTO'23), the lattice-based blind signatures Blaze+ by Alkeilani et al. (ACISP'20) and BlindOR by Alkeilani et al. (CANS'20). In this work, we provide a simple and novel attack on blind signatures based on identification protocols performing parallel repetition to reduce the soundness error. Our attack translates to a polynomial time break for the $\ell$-concurrent unforgeability of CSI-Otter, Blaze+, and BlindOR for $\ell = \mathsf{poly}(\lambda)$. More formally, we define an intermediate problem called Parallel Random inhomogeneities in an Overdetermined Solvable system of linear equations (pROS) problem and show that an attack against pROS implies an attack to the above blind signatures. One takeaway of our finding is that while parallel repetition allows to exponentially reduce the soundness error of an identification protocol, this has minimal effect on the resulting blind signature. Our attack is concretely very efficient and for instance breaks $4$-concurrent unforgeability of CSI-Otter in time roughly $2^{34}$ hash computations.
Last updated:  2023-10-16
Verifiable Encryption from MPC-in-the-Head
Uncategorized
Akira Takahashi and Greg Zaverucha
Show abstract
Uncategorized
Verifiable encryption (VE) is a protocol where one can provide assurance that an encrypted plaintext satisfies certain properties, or relations. It is an important building block in cryptography with many useful applications, such as key escrow, group signatures, optimistic fair exchange, and others. However, the majority of previous VE schemes are restricted to instantiation with specific public-key encryption schemes or relations. In this work, we propose a novel framework that realizes VE protocols using zero-knowledge proof systems based on the MPC-in-the-head paradigm (Ishai et al. STOC 2007). Our generic compiler can turn a large class of zero-knowledge proofs into secure VE protocols for any secure public-key encryption scheme with the undeniability property, a notion that essentially guarantees binding of encryption when used as a commitment scheme. Our framework is versatile: because the circuit proven by the MPC-in-the-head prover is decoupled from a complex encryption function, the work of the prover is focused on proving the encrypted data satisfies the relation, not the proof of plaintext knowledge. Hence, our approach allows for instantiation with various combinations of properties about the encrypted data and encryption functions. We then consider concrete applications, to demonstrate the efficiency of our framework, by first giving a new approach and implementation to verifiably encrypt discrete logarithms in any prime order group more efficiently than was previously known. Then we give the first practical verifiable encryption scheme for AES keys with post-quantum security, along with an implementation and benchmarks.
Last updated:  2023-10-16
A one-query lower bound for unitary synthesis and breaking quantum cryptography
Alex Lombardi, Fermi Ma, and John Wright
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any $n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries $U$ such that no quantum polynomial-time oracle algorithm $A^f$ can implement $U$, even approximately, if it only makes one (quantum) query to $f$. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries $A^{f}$. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary $A^f$. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.
Last updated:  2023-10-16
Weakening Assumptions for Publicly-Verifiable Deletion
James Bartusek, Dakshita Khurana, Giulio Malavolta, Alexander Poremba, and Michael Walter
We develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state generators, if we allow the public verification key to be quantum). Previously, similar compilers either relied on the use of indistinguishability obfuscation (Bartusek et. al., ePrint:2023/265) or almost-regular one-way functions (Bartusek, Khurana and Poremba, arXiv:2303.08676).
Last updated:  2023-10-16
Revocable Cryptography from Learning with Errors
Prabhanjan Ananth, Alexander Poremba, and Vinod Vaikuntanathan
Quantum cryptography leverages many unique features of quantum information in order to construct cryptographic primitives that are oftentimes impossible classically. In this work, we build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before. We define and construct several fundamental cryptographic primitives with key-revocation capabilities, namely pseudorandom functions, secret-key and public-key encryption, and even fully homomorphic encryption, assuming the quantum subexponential hardness of the learning with errors problem. Central to all our constructions is our approach for making the Dual-Regev encryption scheme (Gentry, Peikert and Vaikuntanathan, STOC 2008) revocable.
Last updated:  2023-10-16
Publicly-Verifiable Deletion via Target-Collapsing Functions
James Bartusek, Dakshita Khurana, and Alexander Poremba
We build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for hash functions, analogous to how second preimage resistance weakens collision resistance; that is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image. We show that target-collapsing hashes enable publicly-verifiable deletion (PVD), proving conjectures from [Poremba, ITCS'23] and demonstrating that the Dual-Regev encryption (and corresponding fully homomorphic encryption) schemes support PVD under the LWE assumption. We further build on this framework to obtain a variety of primitives supporting publicly-verifiable deletion from weak cryptographic assumptions, including: - Commitments with PVD assuming the existence of injective one-way functions, or more generally, almost-regular one-way functions. Along the way, we demonstrate that (variants of) target-collapsing hashes can be built from almost-regular one-way functions. - Public-key encryption with PVD assuming trapdoored variants of injective (or almost-regular) one-way functions. We also demonstrate that the encryption scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt'23] based on pseudorandom group actions has PVD. - $X$ with PVD for $X \in \{$attribute-based encryption, quantum fully-homomorphic encryption, witness encryption, time-revocable encryption$\}$, assuming $X$ and trapdoored variants of injective (or almost-regular) one-way functions.
Last updated:  2023-10-16
cqlin: Efficient linear operations on KZG commitments with cached quotients
Liam Eagen and Ariel Gabizon
Given two KZG-committed polynomials $f(X),g(X)\in \mathbb{F}_{<n}[X]$, a matrix $M\in \mathbb{F}^{n\times n}$, and subgroup $H\subset \mathbb{F}^*$ of order $n$, we present a protocol for checking that $f|_{H}\cdot M = g|_{H}$. After preprocessing, the prover makes $O(n)$ field and group operations. This presents a significant improvement over the lincheck protocols in [CHMMVW, COS], where the prover's run-time (also after preprocessing) was quasilinear in the number of non-zeroes of $M$, which could be $n^2$.
Last updated:  2023-10-16
Lightweight but Not Easy: Side-channel Analysis of the Ascon Authenticated Cipher on a 32-bit Microcontroller
Léo Weissbart and Stjepan Picek
Ascon is a recently standardized suite of symmetric cryptography for authenticated encryption and hashing algorithms designed to be lightweight. The Ascon scheme has been studied since it was introduced in 2015 for the CAESAR competition, and many efforts have been made to transform this hardware-oriented scheme to work with any embedded device architecture. Ascon is designed with side-channel resistance in mind and can also be protected with countermeasures against side-channel analysis. Up to now, the effort of side-channel analysis is mainly put on hardware implementations, with only a few studies being published on the real-world side-channel security of software implementations. In this paper, we give a comprehensive view of the side-channel security of Ascon implemented on a 32-bit microcontroller for both the reference and a protected implementation. We show different potential leakage functions that can lead to real-world leakages and demonstrate the most potent attacks that can be obtained with the corresponding leakage functions. We present our results using correlation power analysis (CPA) and deep learning-based side-channel analysis and provide a practical estimation of the efforts needed for an attacker to recover the complete key used for authenticated encryption. Our results show that the reference implementation is not side-channel secure since an attacker can recover the full key with 8,000 traces using CPA and around 1,000 traces with deep learning analysis. While second-order CPA cannot recover any part of the secret, deep learning side-channel analysis can recover partial keys with 800 traces on the protected implementation. Unfortunately, the model used for multi-task key recovery lacks the generalization to correctly recover all partial keys for the full key attack.
Last updated:  2023-10-16
Verifiable Mix-Nets and Distributed Decryption for Voting from Lattice-Based Assumptions
Diego F. Aranha, Carsten Baum, Kristian Gjøsteen, and Tjerand Silde
Cryptographic voting protocols have recently seen much interest from practitioners due to their (planned) use in countries such as Estonia, Switzerland, France, and Australia. Practical protocols usually rely on tested designs such as the mixing-and-decryption paradigm. There, multiple servers verifiably shuffle encrypted ballots, which are then decrypted in a distributed manner. While several efficient protocols implementing this paradigm exist from discrete log-type assumptions, the situation is less clear for post-quantum alternatives such as lattices. This is because the design ideas of the discrete log-based voting protocols do not carry over easily to the lattice setting, due to specific problems such as noise growth and approximate relations. This work proposes a new verifiable secret shuffle for BGV ciphertexts and a compatible verifiable distributed decryption protocol. The shuffle is based on an extension of a shuffle of commitments to known values which is combined with an amortized proof of correct re-randomization. The verifiable distributed decryption protocol uses noise drowning, proving the correctness of decryption steps in zero-knowledge. Both primitives are then used to instantiate the mixing-and-decryption electronic voting paradigm from lattice-based assumptions. We give concrete parameters for our system, estimate the size of each component and provide implementations of all important sub-protocols. Our experiments show that the shuffle and decryption protocol is suitable for use in real-world e-voting schemes.
Last updated:  2023-10-16
Formations for the Quantum Random Oracle
Aaram Yun
In the quantum random oracle model, the adversary may make quantum superposition queries to the random oracle. Since even a single query can potentially probe exponentially many points, classical proof techniques are hard to be applied. For example, recording the oracle queries seemed difficult. In 2018, Mark Zhandry showed that, despite the apparent difficulties, it is in fact possible to ‘record’ the quantum queries. He has defined the compressed oracle, which is indistinguishable from the quantum random oracle, and records information the adversary has gained through the oracle queries. It is a technically subtle work, which we believe to be a challenging work to grasp fully. Our aim is to obtain a mathemathically clean, simple reinterpretation of the compressed oracle technique. For each partial function, we define what we call the formation and the completion of that partial function. The completions describe what happens to the real quantum random oracle, and the formations describe what happens to the compressed oracle. We will show that the formations are 'isomorphic' to the completions, giving an alternative proof that the compressed oracle is indistinguishable from the quantum random oracle.
Last updated:  2023-10-16
A Black Box Attack Using Side Channel Analysis and Hardware Trojans
Raja Adhithan Radhakrishnan
The emergence of hardware trojans as significant threats in various aspects of hardware design, including Firmware, open-source IP, and PCB design, has raised serious concerns. Simultaneously, AI technologies have been employed to simplify the complexity of Side Channel Analysis (SCA) attacks. Due to the increasing risk posed by these threats, it becomes essential to test hardware by considering all possible attack vectors. This paper aims to propose a black box attack using side channel analysis with the aid of hardware trojan insertion. The objective is to emphasize the necessity of side channel-based testing to defend against such attacks. The proposed attack can be executed in FPGA, ASIC, and microcontroller designs. The paper is primarily focused on Verilog design based hardware trojan insertion, and a small example demonstration is provided to illustrate this attack. Keywords:
Last updated:  2023-10-16
Synchronous Distributed Key Generation without Broadcasts
Nibesh Shrestha, Adithya Bhat, Aniket Kate, and Kartik Nayak
Distributed key generation (DKG) is an important building block in designing many efficient distributed protocols. In this work, we initiate the study of communication complexity and latency of distributed key generation protocols under a synchronous network in a point-to-point network. Our key result is the first synchronous DKG protocol for discrete log-based cryptosystems with $O(\kappa n^3)$ communication complexity ($\kappa$ denotes a security parameter) that tolerates $t < n/2$ Byzantine faults among $n$ parties. We show two variants of the protocol: a deterministic protocol with $O(t\Delta)$ latency and randomized protocol with $O(\Delta)$ latency in expectation where $\Delta$ denotes the bounded synchronous delay. In the process of achieving our results, we design (1) a gradecast protocol with optimal communication complexity of $O(\kappa n^2)$ for linear-sized inputs and latency of $O(\Delta)$, (2) a primitive called ``recoverable set of shares'' for ensuring recovery of shared secrets, (3) an oblivious leader election protocol with $O(\kappa n^3)$ communication and $O(\Delta)$ latency, and (4) a multi-valued validated Byzantine agreement (MVBA) protocol with $O(\kappa n^3)$ communication complexity for linear-sized inputs and $O(\Delta)$ latency in expectation. Each of these primitives may be of independent interest.
Last updated:  2023-10-15
Finding All Impossible Differentials When Considering the DDT
Kai Hu, Thomas Peyrin, and Meiqin Wang
Impossible differential (ID) cryptanalysis is one of the most important attacks on block ciphers. The Mixed Integer Linear Programming (MILP) model is a popular method to determine whether a specific difference pair is an ID. Unfortunately, due to the huge search space (approximately $2^{2n}$ for a cipher with a block size $n$ bits), we cannot leverage this technique to exhaust all difference pairs, which is a well-known long-standing problem. In this paper, we propose a systematic method to find all IDs for SPN block ciphers. The idea is to partition the whole difference pair space into lots of small disjoint sets, each of which has a representative difference pair. All difference pairs in one small set are possible if its representative pair is possible, and this can be conveniently checked by the MILP model. In this way, the overall search space is drastically reduced to a practical size by excluding the sets containing no IDs. We then examine the remaining difference pairs to identify all IDs (if some IDs exist). If our method cannot find any ID, the target cipher is proved free of ID distinguishers. Our method works especially well for SPN ciphers with block size 64. We apply our method to SKINNY-64 and successfully find all 432 and 12 truncated IDs (we find all IDs but all of them can be assembled into certain truncated IDs) for 11 and 12 rounds, respectively. We also prove, for the first time, that 13-round SKINNY-64 is free of ID distinguishers even when considering the differential transitions through the Difference Distribution Table (DDT). Similarly, we find all 12 truncated IDs (all IDs are assembled into 12 truncated IDs) for 13-round CRAFT and prove there is no ID for 14 rounds. For SbPN cipher GIFT-64, we prove that there is no ID for 8 rounds. For SPN ciphers with larger block sizes, we show that our idea is also useful to strengthen the current search methods. For example, if we consider the Sbox to be ideal and only consider the branch number information of the diffusion matrix, we can find all 6,750 truncated IDs for 6-round Rijndael-192 in 1 second and prove that there is no truncated ID for 7 rounds. Previously, we need to solve approximately $2^{48}$ MILP models to achieve the same goal. For GIFT-128, we exhausted all difference patterns that have an active superbox in the plaintext and ciphertext and proved there is no ID of such patterns for 8 rounds. Although we have searched for a larger or even full space for IDs, no longer ID distinguishers have been found. This implies the reasonableness of the intuition that a small number (usually one or two) of active bits/words at the beginning and end of an ID will be the longest.
Last updated:  2023-10-15
Behemoth: transparent polynomial commitment scheme with constant opening proof size and verifier time
István András Seres and Péter Burcsi
Polynomial commitment schemes are fundamental building blocks in numerous cryptographic protocols such as verifiable secret sharing, zero-knowledge succinct non-interactive arguments, and many more. The most efficient polynomial commitment schemes rely on a trusted setup which is undesirable in trust-minimized applications, e.g., cryptocurrencies. However, transparent polynomial commitment schemes are inefficient (polylogarithmic opening proofs and/or verification time) compared to their trusted counterparts. It has been an open problem to devise a transparent, succinct polynomial commitment scheme or prove an impossibility result in the transparent setting. In this work, for the first time, we create a transparent, constant-size polynomial commitment scheme called Behemoth with constant-size opening proofs and a constant-time verifier. The downside of Behemoth is that it employs a cubic prover in the degree of the committed polynomial. We prove the security of our scheme in the generic group model and discuss parameter settings in which it remains practical even for the prover.
Last updated:  2023-10-15
Lattice-Based Polynomial Commitments: Towards Asymptotic and Concrete Efficiency
Giacomo Fenzi, Hossein Moghaddas, and Ngoc Khanh Nguyen
Polynomial commitments schemes are a powerful tool that enables one party to commit to a polynomial $p$ of degree $d$, and prove that the committed function evaluates to a certain value $z$ at a specified point $u$, i.e. $p(u) = z$, without revealing any additional information about the polynomial. Recently, polynomial commitments have been extensively used as a cryptographic building block to transform polynomial interactive oracle proofs (PIOPs) into efficient succinct arguments. In this paper, we propose a lattice-based polynomial commitment that achieves succinct proof size and verification time in the degree d of the polynomial. Extractability of our scheme holds in the random oracle model under a natural ring version of the BASIS assumption introduced by Wee and Wu (EUROCRYPT 2023). Unlike recent constructions of polynomial commitments by Albrecht et al. (CRYPTO 2022), and by Wee and Wu, we do not require any expensive preprocessing steps, which makes our scheme particularly attractive as an ingredient of a PIOP compiler for succinct arguments. We further instantiate our polynomial commitment, together with the Marlin PIOP (Eurocrypt 2020), to obtain a publicly-verifiable trusted-setup succinct argument for Rank-1 Constraint System (R1CS). Performance-wise, we achieve 17MB proof size for $2^{20}$ constraints, which is 15X smaller than currently the only publicly-verifiable lattice-based SNARK proposed by Albrecht et al.
Last updated:  2023-10-15
Improved Progressive BKZ with Lattice Sieving and a Two-Step Mode for Solving uSVP
Wenwen Xia, Leizhang Wang, GengWang, Dawu Gu, and Baocang Wang
The unique Shortest Vector Problem (uSVP) is one of the core hard problems in lattice-based cryptography. In NIST PQC standardization (Kyber, Dilithium), leaky-LWE-Estimator is used to estimate the hardness of LWE-based cryptosystems by reducing LWE to uSVP and considers the primal attack using Progressive BKZ (ProBKZ). ProBKZ trivially increases blocksize β and lifts the shortest vector in the final BKZ block to find the unique shortest vector in the full lattice. In this paper, we show that a ProBKZ algorithm as above (we call it a BKZ-only mode) is not the best way to solve uSVP. So we present a two-step mode to solve it, where the ProBKZ algorithm is followed by a sieving algorithm with the dimension larger than the blocksize of BKZ. While instantiating our two-step mode with the sieving algorithm Pump and Pump-and-jump BKZ (PnjBKZ) presented in G6K, which are the state-of-art sieving and BKZ implementations, we show that our algorithm is not only better than the BKZ-only mode but also better than the heuristic uSVP solving algorithm in G6K. However, a ProBKZ with the heuristic parameter selection in leaky-LWE-Estimator or the optimized parameter selection in the literature (Yoshinori Aono et al. at Asiacrypt 2016), is insufficient in optimizing the efficiency of a two-step solving algorithm. To find the best param- eters, we design a PnjBKZ simulator which allows the choice of value jump to be more than 1. Based on the newly designed simulator, we give a blocksize and jump strategy selection algorithm, which can achieve the best simulated efficiency in solving uSVP instances. Combining all the things above, we get a new lattice solving algorithm called Improved Progressive PnjBKZ (ProPnjBKZ for short). We test the efficiency of our ProPnjBKZ with the TU Darmstadt LWE Challenge. The experiment result shows that our ProPnjBKZ is 7.6∼12.9 times more efficient than the heuristic uSVP solving algorithm in G6K. Besides, we break the TU Darmstadt LWE Challenges with (n, α) ∈{(40, 0.035), (40, 0.040), (50, 0.025), (55, 0.020), (90, 0.005)}. Finally, we give a newly refined security estimator of LWE. The evaluation results indicate that the concrete hardness of the lattice-based NIST candidate schemes from LWE primal attack will decrease by 1.9∼4.2 bits when using our optimized blocksize and jump selection strategy and two-step solving mode. In addition, when using the list-decoding technology proposed by MATZOV in 2022, it further decreased by 8∼10.7 bits.
Last updated:  2023-10-14
Discrete Logarithm Factory
Haetham AL ASWAD, Cécile PIERROT, and Emmanuel THOMÉ
The Number Field Sieve and its variants are the best algorithms to solve the discrete logarithm problem in finite fields. The Factory variant accelerates the computation when several prime fields are targeted. This article adapts the Factory variant to non-prime finite fields of medium and large characteristic. We combine this idea with two other variants of NFS, namely the tower and special variant. This combination leads to improvements in the asymptotic complexity. Besides, we lay out estimates of the practicality of this method for 1024-bit targets and extension degree $6$.
Last updated:  2023-10-14
Secure Noise Sampling for DP in MPC with Finite Precision
Hannah Keller, Helen Möllering, Thomas Schneider, Oleksandr Tkachenko, and Liang Zhao
Using secure multi-party computation (MPC) to generate noise and add this noise to a function output allows individuals to achieve formal differential privacy (DP) guarantees without needing to trust any third party or sacrifice the utility of the output. However, securely generating and adding this noise is a challenge considering real-world implementations on finite-precision computers, since many DP mechanisms guarantee privacy only when noise is sampled from continuous distributions requiring infinite precision. We introduce efficient MPC protocols that securely realize noise sampling for several plaintext DP mechanisms that are secure against existing precision-based attacks: the discrete Laplace and Gaussian mechanisms, the snapping mechanism, and the integer-scaling Laplace and Gaussian mechanisms. Due to their inherent trade-offs, the favorable mechanism for a specific application depends on the available computation resources, type of function evaluated, and desired (epsilon,delta)-DP guarantee. The benchmarks of our protocols implemented in the state-of-the-art MPC framework MOTION (Braun et al., TOPS'22) demonstrate highly efficient online runtimes of less than 32 ms/query and down to about 1ms/query with batching in the two-party setting. Also the respective offline phases are practical, requiring only 51 ms to 5.6 seconds/query depending on the batch size.
Last updated:  2023-10-14
ModHE: Modular Homomorphic Encryption Using Module Lattices: Potentials and Limitations
Anisha Mukherjee, Aikata Aikata, Ahmet Can Mert, Yongwoo Lee, Sunmin Kwon, Maxim Deryabin, and Sujoy Sinha Roy
The promising field of homomorphic encryption enables functions to be evaluated on encrypted data and produce results that mimic the same computations done on plaintexts. It, therefore, comes as no surprise that many ventures at constructing homomorphic encryption schemes have come into the limelight in recent years. Most popular are those that rely on the hard lattice problem, called the Ring Learning with Errors problem (RLWE). One major limitation of these homomorphic encryption schemes is that in order to securely increase the maximum multiplicative depth, they need to increase the polynomial-size thereby also increasing the complexity of the design. We aim to bridge this gap by proposing a homomorphic encryption (HE) scheme based on the Module Learning with Errors problem (MLWE), ModHE that allows us to break the big computations into smaller ones. Given the popularity of module lattice-based post-quantum schemes, it is an evidently interesting research endeavor to also formulate module lattice-based homomorphic encryption schemes. While our proposed scheme is general, as a case study, we port the well-known RLWE-based CKKS scheme to the MLWE setting. The module version of the scheme completely stops the polynomial-size blowups when aiming for a greater circuit depth. Additionally, it presents greater opportunities for designing flexible, reusable, and parallelizable hardware architecture. A hardware implementation is provided to support our claims. We also acknowledge that as we try to decrease the complexity of computations, the amount of computations (such as relinearizations) increases. We hope that the potential and limitations of using such a hardware-friendly scheme will spark further research.
Last updated:  2023-10-14
Identity-Based Matchmaking Encryption, Revisited: Strong Security and Practical Constructions from Standard Classical and Post-Quantum Assumptions
Sohto Chiku, Keitaro Hashimoto, Keisuke Hara, and Junji Shikata
Identity-based matchmaking encryption (IB-ME) [Ateniese et al. Crypto 2019] allows users to communicate privately in an anonymous and authenticated manner. After the seminal paper by Ateniese et al., a lot of work has been done on the security and construction of IB-ME. In this work, we revisit the security definitions and construction of IB-ME and provide the following three contributions. -- First, we embark on the task of classifying the existing security notions of IB-ME. We systematically categorize privacy into three core categories (CPA, CCA, and privacy in the case of mismatch) and authenticity into four categories (NMA and CMA both against insiders and outsiders). In particular, we reconsider privacy when the sender's identity is mismatched during decryption, considered as ``enhanced privacy''~[Francati et al., INDOCRYPT 2021], and provide a new simple security game, called mismatch security, that captures the essence of it. This structured framework not only facilitates more precise comparisons between different IB-ME schemes, but also serves as a valuable tool for evaluating the security of newly proposed schemes. -- Second, we propose a highly efficient and strongly secure IB-ME scheme from the bilinear Diffie-Hellman assumption in the random oracle model. The scheme is based on the Ateniese et al. scheme, but we introduce several techniques to improve its security and efficiency. Especially, we found that the Fujisaki-Okamoto transformation enhances not only privacy but also authenticity. As a result, we obtain a scheme that offers a more compact decryption key and ciphertext than the Ateniese et al. scheme, while achieving CCA and CMA, and mismatch security. -- Third, we propose a new generic construction of IB-ME from anonymous identity-based encryption, identity-based signature, and reusable extractors. Our construction not only achieves CCA, CMA, and mismatch security, but is also the most efficient among existing generic constructions. Through this construction, we obtain various IB-ME schemes from both classical and post-quantum assumptions. For example, we obtain a more efficient scheme from the symmetric external Diffie-Hellman assumption in the standard model, and a practical scheme from lattices in the quantum random oracle model whose secret keys and ciphertexts are less than 5 kilobytes. Moreover, our generic construction produces the first pairing-free IB-ME scheme in the standard model and the first tightly secure lattice-based IB-ME scheme in the quantum random oracle model.
Last updated:  2023-10-14
Multi-Party Homomorphic Secret Sharing and Sublinear MPC from Sparse LPN
Quang Dao, Yuval Ishai, Aayush Jain, and Huijia Lin
Over the past few years, homomorphic secret sharing (HSS) emerged as a compelling alternative to fully homomorphic encryption (FHE), due to its feasibility from an array of standard assumptions and its potential efficiency benefits. However, all known HSS schemes, with the exception of schemes built from FHE or indistinguishability obfuscation (iO), can only support two or four parties. In this work, we give the first construction of a multi-party HSS scheme for a non-trivial function class, from an assumption not known to imply FHE. In particular, we construct an HSS scheme for an arbitrary number of parties with an arbitrary corruption threshold, supporting evaluations of multivariate polynomials of degree $\log / \log \log$ over arbitrary finite fields. As a consequence, we obtain a secure multiparty computation (MPC) protocol for any number of parties, with (slightly) sub-linear per-party communication of roughly $O(S / \log \log S)$ bits when evaluating a layered Boolean circuit of size $S$. Our HSS scheme relies on the Sparse Learning Parity with Noise assumption, a standard variant of LPN with a sparse public matrix that has been studied and used in prior works. Thanks to this assumption, our construction enjoys several unique benefits. In particular, it can be built on top of any linear secret sharing scheme, producing noisy output shares that can be error-corrected by the decoder. This yields HSS for low-degree polynomials with optimal download rate. Unlike prior works, our scheme also has a low computation overhead in that the per-party computation of a constant degree polynomial takes $O(M)$ work, where $M$ is the number of monomials.
Last updated:  2023-10-14
Analysis of one semi-quantum-honest key agreement scheme in MSTSA structure without entanglement
Zhengjun Cao and Lihua Liu
We show that the key agreement scheme [Quantum Inf. Process., 20:188, 2021] is flawed. (1) It requires that the quantum channel must be intact so as to keep the transferred photon sequences complete and undamaged, even if the channel is tapped. But this is unrealistic because of quantum non-cloning theorem. (2) The user's capability is artificially assumed, who can measure a hybrid photon sequence only with $Z$-basis, unable to measure with $X$-basis. (3) It requires an authenticated classical channel for the negotiation between Alice and Server$_B$. If such a channel is available, the scheme can be greatly simplified using the mechanism in BB84 protocol.
Last updated:  2023-10-13
One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
Yanyi Liu and Rafael Pass
Consider the recently introduced notion of \emph{probabilistic time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al, CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k. We show the equivalence of the following: - MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable distribution D; - MpK^{poly}P is (mildly) hard-on-average w.r.t. the \emph{uniform} distribution; - Existence of one-way functions. As far as we know, this yields the first natural class of problems where hardness with respect to any samplable distribution is equivalent to hardness with respect to the uniform distribution. Under standard derandomization assumptions, we can show the same result also w.r.t. the standard notion of time-bounded Kolmogorov complexity, K^t.
Last updated:  2023-10-13
M&M'S: Mix and Match Attacks on Schnorr-type Blind Signatures with Repetition
Khue Do, Lucjan Hanzlik, and Eugenio Paracucchi
Blind signatures allow the issuing of signatures on messages chosen by the user so that they ensure $\mathit{blindness}$ of the message against the signer. Moreover, a malicious user cannot output $\ell+1$ signatures while only finishing $\ell$ signing sessions. This notion, called $\mathit{one}$-$\mathit{more}$ unforgeability, comes in two flavors supporting either $\mathit{sequential}$ or $\mathit{concurrent}$ sessions. In this paper, we investigate the security of a class of blind signatures constructed from Sigma-protocols with small challenge space $\mathcal{C}_{\Sigma}$ (i.e., polynomial in the security parameter), using $k$ repetitions of the protocol to decrease the chances of a cheating prover. This class of schemes includes, among others, the Schnorr blind signature scheme with bit challenges and the recently proposed isogeny-based scheme CSI-Otter (Crypto'23), as well as potential blind signatures designed from assumptions with the well-known Sigma-protocol for the graph-isomorphism problem (e.g., Lattice Isomorphism Problem). For this class of blind signatures, we show a $\mathit{polynomial}$-$\mathit{time}$ attack that breaks one-more unforgeability for any $\ell \geq k$ concurrent sessions in time $O(k \cdot |\mathcal{C}_{\Sigma}|)$. Contrary to the ROS attack, ours is generic and does not require any particular algebraic structure. We also propose a computational trade-off, where, for any $t \leq k$, our attack works for $\ell = \frac{k}{t}$ in time $O(\frac{k}{t} \cdot |\mathcal{C}_{\Sigma}|^t)$. The consequences of our attack are as follows. Schemes in the investigated class of blind signatures should not be used concurrently without applying specific transformations to boost the security to support more signing sessions. Moreover, for the parameters proposed for CSI-Otter ($k=128$ and $|\mathcal{C}_{\Sigma}|=2$), the scheme becomes forgeable after 128 concurrent signing sessions for the basic attack and with only eight sessions in our optimized attack. We also show that for those parameters, it is even possible to compute two signatures in around 10 minutes with just one signing session using the computation power of the Bitcoin network. Thus, we show that, for sequential security, the parameter $k$ must be at least doubled in the security parameter for any of the investigated schemes.
Last updated:  2023-10-13
Computing Isogenies of Power-Smooth Degrees Between PPAVs
Jesús-Javier Chi-Domínguez, Amalia Pizarro-Madariaga, and Edgardo Riquelme
The wave of attacks by Castryck and Decru (Eurocrypt, 2023), Maino, Martindale, Panny, Pope and Wesolowski (Eurocrypt, 2023) and Robert (Eurocrypt, 2023), highlight the destructive facet of calculating power-smooth degree isogenies between higher-dimensional abelian varieties in isogeny-based cryptography. Despite those recent attacks, there is still interest in using isogenies but for building protocols on top of higher-dimensional abelian varieties. Examples of such protocols are Public-Key Encryption, Key Encapsulation Mechanism, Verifiable Delay Function, Verifiable Random Function, and Digital Signatures. This work abstracts and proposes a generalization of the strategy technique by Jao, De Feo and Plût (Journal of Mathematical Cryptology, 2014) to give an efficient generic algorithm for computing isogenies between higher-dimensional abelian varieties with kernels being maximal isotropic of power-smooth degree. To illustrate the impact of using such strategy technique, we draft our experiments on the computation of isogenies over two-dimensional abelian varieties determined by a maximal isotropic subgroup of torsion with a power of two or three. Our experiments illustrate a speed-up of 1.25x faster than the state-of-the-art (about 20% of savings).
Last updated:  2023-10-13
Algorithmic Views of Vectorized Polynomial Multipliers – NTRU Prime
Vincent Hwang, Chi-Ting Liu, and Bo-Yin Yang
In this paper, we explore the cost of vectorization for polynomial multiplication with coefficients in $\mathbb{Z}_q$ for an odd prime $q$. If there is a large power of two dividing $q−1$, we can apply radix-2 Cooley–Tukey fast Fourier transforms to multiply polynomials in $\mathbb{Z}_q[x]$. The radix-2 nature admits efficient vectorization. Conversely, if 2 is the only power of two dividing $q−1$, we can apply Schönhage’s and Nussbaumer’s FFTs to craft radix-2 roots of unity, but these double the number of coefficients. We show how to avoid this doubling while maintaining vectorization friendliness with Good–Thomas, Rader’s, and Bruun’s FFTs. In particular, we exploit the existing Fermat-prime factor of $q − 1$ for Rader’s FFT and the power-of-two factor of $q + 1$ for Bruun’s FFT. We implement these ideas for the NTRU Prime instances ntrulpr761/sntrup761, operating over the coefficient ring $\mathbb{Z}_{4591}$ on a Cortex-A72. sntrup761 is currently used in OpenSSH 9.0 by default. Our polynomial multiplication outperforms the state-of-the-art vector-optimized implementation by 6.1×. For ntrulpr761, our keygen, encap, and decap are 2.98×, 2.79×, and 3.07× faster than the state-of-the-art vector-optimized implementation. For sntrup761, we outperform the reference implementation significantly.
Last updated:  2023-10-13
A Single-Trace Message Recovery Attack on a Masked and Shuffled Implementation of CRYSTALS-Kyber
Sönke Jendral, Kalle Ngo, Ruize Wang, and Elena Dubrova
Last year CRYSTALS-Kyber was chosen by NIST as a new, post-quantum secure key encapsulation mechanism to be standardized. This makes it important to assess the resistance of CRYSTALS-Kyber implementations to physical attacks. Pure side-channel attacks on post-quantum cryptographic algorithms have already been well-explored. In this paper, we present an attack on a masked and shuffled software implementation of CRYSTALS-Kyber that combines fault injection with side-channel analysis. First, a voltage fault injection is performed to bypass the shuffling. We found settings that consistently glitch the desired instructions without crashing the device. After the successful fault injection, a deep learning-assisted profiled power analysis based on the Hamming weight leakage model is used to recover the message (shared key). We propose a partial key enumeration method that allows us to significantly increase the success rate of message recovery (from 0.122 without enumeration to 0.887 with 32 enumerated bits).
Last updated:  2023-10-13
A State-Separating Proof for Yao’s Garbling Scheme
Chris Brzuska and Sabine Oechsner
Secure multiparty computation enables mutually distrusting parties to compute a public function of their secret inputs. One of the main approaches for designing MPC protocols are garbled circuits whose core component is usually referred to as a garbling scheme. In this work, we revisit the security of Yao’s garbling scheme and provide a modular security proof which composes the security of multiple layer garblings to prove security of the full circuit garbling. We perform our security proof in the style of state-separating proofs (ASIACRYPT 2018).
Last updated:  2023-10-13
On the Round Complexity of Asynchronous Crusader Agreement
Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail. Instead, we show new, tight, rather surprising round complexity upper bounds for Byzantine fault tolerant BCA with and without a PKI setup.
Last updated:  2023-10-13
An algebraic attack for forging signatures of MPPK/DS
Hao Guo
We give an algebraic attack to forge the signature of a scheme called MPPK/DS, which can be achieved by solving a linear system in 5 variables with coefficients on $\mathbb{Z}/2^x q \mathbb{Z}$ for some odd prime $q$ and $x ≥ 1$.
Last updated:  2023-10-13
How to Rationally Select Your Delegatee in PoS
Yuzhe Zhang, Qin Wang, Shiping Chen, and Chen Wang
This paper centers around a simple yet crucial question for everyday users: How should one choose their delegated validators within proof-of-stake (PoS) protocols, particularly in the context of Ethereum 2.0? This has been a long-overlooked gap, as existing studies have primarily focused on inter-committee (validator set) behaviors and activities, while neglecting the dynamic formation of committees, especially for individual stakeholders seeking reliable validators. Our study bridges this gap by diving into the delegation process (normal users delegate their small-value tokens to delegatees who later act as validators) before entering an actual consensus phase. We propose a Bayesian model to quantify normal users' trust in delegatees, which we further incorporate into a game-theoretical model to simulate users' reactions against a set of critical factors identified through extensive research (including 10+ staking service providers as well as 30+ PoS blockchains). Our results reveal that users tend to choose their delegatees and utilize their tokens by carefully weighing the delegation cost, the behaviors of other users, and the reputation of delegatees, ultimately reaching a Nash equilibrium. Unfortunately, the collective trend significantly increases the likelihood of token concentration on a small number of delegatees.
Last updated:  2023-10-13
How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations
Hanjun Li and Tianren Liu
The study of garbling arithmetic circuits is initiated by Applebaum, Ishai, and Kushilevitz [FOCS'11], which can be naturally extended to mixed circuits. The basis of mixed circuits includes Boolean operations, arithmetic operations over a large ring and bit-decomposition that converts an arithmetic value to its bit representation. We construct efficient garbling schemes for mixed circuits. In the random oracle model, we construct two garbling schemes: $\bullet$ The first scheme targets mixed circuits modulo some $N\approx 2^b$. Addition gates are free. Each multiplication gate costs $O(\lambda \cdot b^{1.5})$ communication. Each bit-decomposition costs $O(\lambda \cdot b^{2} / \log{b})$. $\bullet$ The second scheme targets mixed circuit modulo some $N\approx 2^b$. Each addition gate and multiplication gate costs $O(\lambda \cdot b \cdot \log b / \log \log b)$. Every bit-decomposition costs $O(\lambda \cdot b^2 / \log b)$. Our schemes improve on the work of Ball, Malkin, and Rosulek [CCS'16] in the same model. Additionally relying on the DCR assumption, we construct in the programmable random oracle model a more efficient garbling scheme targeting mixed circuits over $\mathbb{Z}_{2^b}$, where addition gates are free, and each multiplication or bit-decomposition gate costs $O(\lambda_{\text{DCR}} \cdot b)$ communication. We improve on the recent work of Ball, Li, Lin, and Liu [Eurocrypt'23] which also relies on the DCR assumption.
Last updated:  2023-10-13
Realizing Flexible Broadcast Encryption: How to Broadcast to a Public-Key Directory
Rachit Garg, George Lu, Brent Waters, and David J. Wu
Suppose a user wants to broadcast an encrypted message to $K$ recipients. With public-key encryption, the sender would construct $K$ different ciphertexts, one for each recipient. The size of the broadcasted message then scales linearly with $K$. A natural question is whether the sender can encrypt the message with a ciphertext whose size scales sublinearly with the number of recipients. Broadcast encryption offers one solution to this problem, but at the cost of introducing a central trusted party who issues keys to different users (and correspondingly, has the ability to decrypt all ciphertexts). Recently, several works have introduced notions like distributed broadcast encryption and flexible broadcast encryption, which combine the decentralized, trustless model of traditional public-key encryption with the efficiency guarantees of broadcast encryption. In the specific case of a flexible broadcast encryption scheme, users generate their own public/private keys and can then post their public key in any public-key directory. Subsequently, a user can encrypt to an arbitrary set of user public keys with a ciphertext whose size scales polylogarithmically with the number of public keys in the broadcast set. A distributed broadcast encryption scheme is a more restrictive primitive where each public key is also associated with an index, and one can only encrypt to a set of public keys corresponding to different indices. In this work, we introduce a generic compiler that takes any distributed broadcast encryption scheme and produces a flexible broadcast encryption scheme. Moreover, whereas existing concretely-efficient constructions of distributed broadcast encryption have public keys whose size scales with the maximum number of users in the system, our resulting flexible broadcast encryption scheme has the appealing property that the size of each public key scales with the size of the maximum broadcast set. We provide an implementation of the flexible broadcast encryption scheme obtained by applying our compiler to the distributed broadcast encryption scheme of Kolonelos, Malavolta, and Wee (ASIACRYPT 2023). With our scheme, a sender can encrypt a 128-bit symmetric key to a set of over 1000 recipients (from a directory with a million users) with a 2 KB ciphertext. This is 16$\times$ smaller than separately encrypting to each user using standard ElGamal encryption. The cost is that the user public keys in flexible broadcast encryption are much larger (50 KB) compared to standard ElGamal public keys (32 bytes). Compared to the similarly-instantiated distributed broadcast encryption scheme, we achieve a 32$\times$ reduction in the user's public key size (50 KB vs. 1.6 MB) without changing the ciphertext size. Thus, flexible broadcast encryption provides an efficient way to encrypt messages to large groups of users at the cost of larger individual public keys (relative to vanilla public-key encryption).
Last updated:  2023-10-12
Unclonable Non-Interactive Zero-Knowledge
Ruta Jawale and Dakshita Khurana
A non-interactive ZK (NIZK) proof enables verification of NP statements without revealing secrets about them. However, an adversary that obtains a NIZK proof may be able to clone this proof and distribute arbitrarily many copies of it to various entities: this is inevitable for any proof that takes the form of a classical string. In this paper, we ask whether it is possible to rely on quantum information in order to build NIZK proof systems that are impossible to clone. We define and construct unclonable non-interactive zero-knowledge proofs (of knowledge) for NP. Besides satisfying the zero-knowledge and proof of knowledge properties, these proofs additionally satisfy unclonability. Very roughly, this ensures that no adversary can split an honestly generated proof of membership of an instance $x$ in an NP language $\mathcal{L}$ and distribute copies to multiple entities that all obtain accepting proofs of membership of $x$ in $\mathcal{L}$. Our result has applications to unclonable signatures of knowledge, which we define and construct in this work; these non-interactively prevent replay attacks.
Last updated:  2023-10-12
Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States
Léo Colisson, Garazi Muguruza, and Florian Speelman
We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexity properties and security guarantees (plain-model/statistical security/unstructured functions…) of the ZK protocol to the resulting OT protocol. Such a construction is unlikely to exist classically as Cryptomania is believed to be different from Minicrypt. In particular, by instantiating our construction using Non-Interactive ZK (NIZK), we provide the first round-optimal (2-message) quantum OT protocol secure in the random oracle model, and round-optimal extensions to string and k-out-of-n OT. At the heart of our construction lies a new method that allows us to prove properties on a received quantum state without revealing additional information on it, even in a non-interactive way, without public-key primitives, and/or with statistical guarantees when using an appropriate classical ZK protocol. We can notably prove that a state has been partially measured (with arbitrary constraints on the set of measured qubits), without revealing any additional information on this set. This notion can be seen as an analog of ZK to quantum states, and we expect it to be of independent interest as it extends complexity theory to quantum languages, as illustrated by the two new complexity classes we introduce, ZKstatesQIP and ZKstatesQMA.
Last updated:  2023-10-12
Anonyma: Anonymous Invitation-Only Registration in Malicious Adversarial Model
Sanaz Taheri Boshrooyeh, Alptekin Küpçü, and Öznur Özkasap
In invitation-based systems, a new user can register upon having a threshold number of invitations issued by the existing members. The newcomer hands his invitations to the system administrator who verifies whether the invitations are issued by legitimate members. This causes the administrator to be aware of who is invited by whom. However, the inviter-invitee relationship is privacy-sensitive information and can lead to inference attacks where the invitee's profile (e.g., political view or location) can be extracted through the profiles of his inviters. Addressing this problem, we propose Anonyma, an anonymous invitation-based system, where a corrupted administrator, who may even collude with a subset of existing members, is not able to figure out who is invited by whom. We formally define and prove the inviter anonymity as well as unforgeability of invitations against a malicious and adaptive adversary. Our design only incurs a constant cost to authenticate a new registration. This is significantly better than similar works where the generation of invitations and verification of new registration cause an overhead linear in the total number of existing members. Besides, Anonyma is efficiently scalable in the sense that once a user joins the system, the administrator can instantly, and without re-keying the existing members, issue credentials for the newcomer to be able to act as an inviter. We additionally design Anonymax, an anonymous cross-network invitation-based system empowering third-party authentication where the invitations issued by the members of one system can be used for registering to another system.
Last updated:  2023-10-12
CryptoZoo: A Viewer for Reduction Proofs
Uncategorized
Chris Brzuska, Christoph Egger, and Kirthivaasan Puniamurthy
Show abstract
Uncategorized
Cryptographers rely on visualization to effectively communicate cryptographic constructions with one another. Visual frameworks such as constructive cryptography (TOSCA 2011), the joy of cryptography (online book) and state-separating proofs (SSPs, Asiacrypt 2018) are useful to communicate not only the construction, but also their proof visually by representing a cryptographic system as graphs. One SSP core feature is the re-use of code, e.g., a package of code might be used in a game and be part of the description of a reduction as well. Thus, in a proof, the linear structure of a paper either requires the reader to turn pages to find definitions or writers to re-state them, thereby interrupting the visual flow of the game hops that are defined by a sequence of graphs. We present an interactive proof viewer for state-separating proofs (SSPs) which addresses the limitations and perform three case studies: The equivalence between simulation-based and game-based notions for symmetric encryption, the security proof of the Goldreich-Goldwasser-Micali construction of a pseudorandom function from a pseudorandom generator, and Brzuska's and Oechsner's SSP formalization of the proof for Yao's garbling scheme.
Last updated:  2023-10-12
Registered FE beyond Predicates: (Attribute-Based) Linear Functions and more
Pratish Datta, Tapas Pal, and Shota Yamada
This paper introduces the first registered functional encryption RFE scheme tailored for linear functions. Distinctly different from classical functional encryption (FE), RFE addresses the key-escrow issue and negates the master key exfiltration attack. Instead of relying on a centralized trusted authority, it introduces a “key curator” - a fully transparent entity that does not retain secrets. In an RFE framework, users independently generate secret keys and subsequently register their respective public keys, along with their authorized functions, with the key curator. This curator consolidates public keys from various users into a unified, concise master public key. For decryption, users occasionally secure helper decryption keys from the key curator, which they use in conjunction way with their private keys. It is imperative that the aggregate public key, helper decryption keys, ciphertexts, and the times for encryption/decryption are polylogarithmic in the number of registered users. All existing RFE designs were confined to predicates where given the correct credentials a user can retrieve the entire payload from a ciphertext or gain no information about it otherwise. Contrarily, our RFE scheme facilitates the computation of linear functions on encrypted content and extraction of only the computation results. Recognizing potential leaks from linear functions, we further enhance our RFE by incorporating an attribute-based access control mechanism. The outcome is the first registered attribute-based linear FE (RABIPFE), which supports access policies depicted as linear secret sharing schemes LSSS. Our proposed schemes are realized in the common reference string (CRS) model as introduced by Hohenberger et al.[EUROCRYPT 2023], employ simple tools and black-box methods. Specifically, our constructs operate in asymmetric prime-order bilinear group regime setting and are proven secure in the generic bilinear group model. Aligning with all pre-existing black-box RFE designs within the CRS model, our schemes cater to a predetermined maximum user count. A notable variant of our RABIPFE scheme also yields the first efficient register ABE (RABE) system for LSSS access policies in asymmetric prime-order bilinear groups. Conclusively, demonstrating feasibility, we formulated an RFE blueprint that supports general functionalities and an infinite user base, leveraging indistinguishability obfuscation and one-way functions.
Last updated:  2023-10-12
Polynomial Time Cryptanalytic Extraction of Neural Network Models
Isaac A. Canales-Martínez, Jorge Chavez-Saab, Anna Hambitzer, Francisco Rodríguez-Henríquez, Nitin Satpute, and Adi Shamir
Billions of dollars and countless GPU hours are currently spent on training Deep Neural Networks (DNNs) for a variety of tasks. Thus, it is essential to determine the difficulty of extracting all the parameters of such neural networks when given access to their black-box implementations. Many versions of this problem have been studied over the last 30 years, and the best current attack on ReLU-based deep neural networks was presented at Crypto’20 by Carlini, Jagielski, and Mironov. It resembles a differential chosen plaintext attack on a cryptosystem, which has a secret key embedded in its black-box implementation and requires a polynomial number of queries but an exponential amount of time (as a function of the number of neurons). In this paper, we improve this attack by developing several new techniques that enable us to extract with arbitrarily high precision all the real-valued parameters of a ReLU-based DNN using a polynomial number of queries and a polynomial amount of time. We demonstrate its practical efficiency by applying it to a full-sized neural network for classifying the CIFAR10 dataset, which has 3072 inputs, 8 hidden layers with 256 neurons each, and about 1.2 million neuronal parameters. An attack following the approach by Carlini et al. requires an exhaustive search over 2^256 possibilities. Our attack replaces this with our new techniques, which require only 30 minutes on a 256-core computer.
Last updated:  2023-10-12
New SIDH Countermeasures for a More Efficient Key Exchange
Andrea Basso and Tako Boris Fouotsa
The Supersingular Isogeny Diffie-Hellman (SIDH) protocol has been the main and most efficient isogeny-based encryption protocol, until a series of breakthroughs led to a polynomial-time key-recovery attack. While some countermeasures have been proposed, the resulting schemes are significantly slower and larger than the original SIDH. In this work, we propose a new countermeasure technique that leads to significantly more efficient and compact protocols. To do so, we introduce the concept of artificially oriented curves, which are curves with an associated pair of subgroups. We show that this information is sufficient to build parallel isogenies and thus obtain an SIDH-like key exchange, while also revealing significantly less information compared to previous constructions. After introducing artificially oriented curves, we formalize several related computational problems and thoroughly assess their presumed hardness. We then translate the SIDH key exchange to the artificially oriented setting, obtaining the key-exchange protocols binSIDH, or binary SIDH, and terSIDH, or ternary SIDH, which respectively rely on fixed-degree and variable-degree isogenies. Lastly, we also provide a proof-of-concept implementation of the proposed protocols. Despite being implemented in a high-level language, terSIDH has very competitive running times, which suggests that terSIDH might be the most efficient isogeny-based encryption protocol.
Last updated:  2023-10-12
Towards Optimally Small Smoothness Bounds for Cryptographic-Sized Twin Smooth Integers and its Isogeny-based Applications
Bruno Sterner
We give a new approach for finding large twin smooth integers. Those twins whose sum is a prime are of interest in the parameter setup of certain isogeny-based cryptosystems such as SQISign. The approach to find such twins is to find two polynomials in $\Q[x]$ that split into a product of small degree factors and differ by $1$; then evaluate them on a particular smooth integer. This was first explored by Costello, Meyer and Naehrig at EUROCRYPT'21 using polynomials that split completely into linear factors which were found from some Diophantine number theory. The polynomials used in this work split into mostly linear factors with the exception of a few quadratic factors. Some of these linear factors are repeated and so the overall smoothness probability is either better or comparable to that of the prior polynomials. We utilise these polynomials to search for large twin smooth integers whose sum is prime. In particular, the smoothness bound of the $384$ and $512$-bit instances that we find are significantly smaller than those found in EUROCRYPT'21.
Last updated:  2023-10-12
Further Improvements of the Estimation of Key Enumeration with Applications to Solving LWE
Alessandro Budroni and Erik Mårtensson
In post-quantum cryptography, Learning With Errors (LWE) is one of the dominant underlying mathematical problems. The dual attack is one of the main strategies for solving the LWE problem, and it has recently gathered significant attention within the research community. A series of studies initially suggested that it might be more efficient than the other main strategy, the primal attack. Then, a subsequent work by Ducas and Pulles (Crypto’23) raised doubts on the estimated complexity of such an approach. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to decrease the estimated cost of this procedure and, hence, of the whole attack both classically and quantumly. In addition, we explore different enumeration strategies to achieve some further improvements. Our work is independent from the questions raised by Ducas and Pulles, which do not concern the estimation of the enumeration procedure in the dual attack. As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptanalysis or even in other research areas.
Last updated:  2023-10-12
FssNN: Communication-Efficient Secure Neural Network Training via Function Secret Sharing
Peng Yang, Zoe L. Jiang, Shiqi Gao, Jiehang Zhuang, Hongxiao Wang, Junbin Fang, Siuming Yiu, Yulin Wu, and Xuan Wang
Privacy-preserving neural network enables multiple parties to jointly train neural network models without revealing sensitive data. However, its practicality is greatly limited due to the low efficiency caused by massive communication costs and a deep dependence on a trusted dealer. In this paper, we propose a communication-efficient secure two-party neural network framework, FssNN, to enable practical secure neural network training and inference. In FssNN, we reduce communication costs of computing neural network operators in the online and offline phases by combining additive secret sharing (SS) and function secret sharing (FSS), and eliminate the dependence on the trusted dealer based on a distributed key generation scheme. First, by integrating correction words and designing a more compact key generation algorithm, we propose a key-reduced distributed comparison function (DCF, a FSS scheme for comparison functions) with the smallest key sizes to enable efficient computation of non-linear layer functions in the offline phase. Secondly, by leveraging the proposed DCF and combining SS and FSS, we construct online-efficient computation protocols for neural network operators, such as Hadamard product, ReLU and DReLU, and reduce the online communication costs to about $1/2$ of that of the state-of-the-art solution. Finally, by utilizing MPC-friendly pseudorandom generators, we propose a distributed DCF key generation scheme to replace the trusted dealer and support a larger input domain than the state-of-the-art solution. Using FssNN, we perform extensive secure training and inference evaluations on various neural network models. Compared with the state-of-the-art solution AriaNN (PoPETs'22), we reduce the communication costs of secure training and inference by approximately $25.4 \%$ and $26.4 \%$ respectively, while keeping the accuracy of privacy-preserving training and inference close to that of plaintext training and inference.
Last updated:  2023-10-12
SoK: Web3 Recovery Mechanisms
Panagiotis Chatzigiannis, Konstantinos Chalkias, Aniket Kate, Easwar Vivek Mangipudi, Mohsen Minaei, and Mainack Mondal
Account recovery enables users to regain access to their accounts when they lose their authentication credentials. While account recovery is well established and extensively studied in the Web2 (traditional web) context, Web3 account recovery presents unique challenges. In Web3, accounts rely on a (cryptographically secure) private-public key pair as their credential, which is not expected to be shared with a single entity like a server owing to security concerns. This makes account recovery in the Web3 world distinct from the Web2 landscape, often proving to be challenging or even impossible. As account recovery has proven crucial for Web2 authenticated systems, various solutions have emerged to address account recovery in the Web3 blockchain ecosystem in order to make it more friendly and accessible to everyday users, without "punishing" users if they make honest mistakes. This study systematically examines existing account recovery solutions within the blockchain realm, delving into their workflows, underlying cryptographic mechanisms, and distinct characteristics. After highlighting the trilemma between usability, security, and availability encountered in the Web3 recovery setting, we systematize the existing recovery mechanisms across several axes which showcase those tradeoffs. Based on our findings, we provide a number of insights and future research directions in this field.
Last updated:  2023-10-11
AutoFHE: Automated Adaption of CNNs for Efficient Evaluation over FHE
Wei Ao and Vishnu Naresh Boddeti
Secure inference of deep convolutional neural networks (CNNs) under RNS-CKKS involves polynomial approximation of unsupported non-linear activation functions. However, existing approaches have three main limitations: 1) Inflexibility: The polynomial approximation and associated homomorphic evaluation architecture are customized manually for each CNN architecture and do not generalize to other networks. 2) Suboptimal Approximation: Each activation function is approximated instead of the function represented by the CNN. 3) Restricted Design: Either high-degree or low-degree polynomial approximations are used. The former retains high accuracy but slows down inference due to bootstrapping operations, while the latter accelerates ciphertext inference but compromises accuracy. To address these limitations, we present AutoFHE, which automatically adapts standard CNNs for secure inference under RNS-CKKS. The key idea is to adopt layerwise mixed-degree polynomial activation functions, which are optimized jointly with the homomorphic evaluation architecture in terms of the placement of bootstrapping operations. The problem is modeled within a multi-objective optimization framework to maximize accuracy and minimize the number of bootstrapping operations. AutoFHE can be applied flexibly on any CNN architecture, and it provides diverse solutions that span the trade-off between accuracy and latency. Experimental evaluation over RNS-CKKS encrypted CIFAR datasets shows that AutoFHE accelerates secure inference by $1.32\times$ to $1.8\times$ compared to methods employing high-degree polynomials. It also improves accuracy by up to 2.56% compared to methods using low-degree polynomials. Lastly, AutoFHE accelerates inference and improves accuracy by $103\times$ and 3.46%, respectively, compared to CNNs under TFHE.
Last updated:  2023-10-11
A reduced set of submatrices for a faster evaluation of the MDS property of a circulant matrix with entries that are powers of two
Dragan Lambić
In this paper a reduced set of submatrices for a faster evaluation of the MDS property of a circulant matrix, with entries that are powers of two, is proposed. A proposition is made that under the condition that all entries of a t × t circulant matrix are powers of 2, it is sufficient to check only its 2x2 submatrices in order to evaluate the MDS property in a prime field. Although there is no theoretical proof to support this proposition at this point, the experimental results conducted on a sample of 100 thousand randomly generated matrices indicate that this proposition is true. There are benefits of the proposed MDS test on the efficiency of search methods for the generation of circulant MDS matrices, regardless of the correctness of this proposition. However, if this proposition is correct, its impact on the speed of search methods for circulant MDS matrices will be huge, which will enable generation of MDS matrices of large sizes. Also, a modified version of the make_binary_powers function is presented. Based on this modified function and the proposed MDS test, some examples of efficient 16 x 16 MDS matrices are presented. Also, an examples of efficient 24 x 24 matrices are generated, whose MDS property should be further validated.
Last updated:  2023-10-11
Dynamic Decentralized Functional Encryption with Strong Security
Ky Nguyen, David Pointcheval, and Robert Schädlich
Decentralized Multi-Client Functional Encryption (DMCFE) extends the basic functional encryption to multiple clients that do not trust each other. They can independently encrypt the multiple inputs to be given for evaluation to the function embedded in the functional decryption key. And they keep control on these functions as they all have to contribute to the generation of the functional decryption keys. Dynamic Decentralized Functional Encryption (DDFE) is the ultimate extension where one can dynamically join the system and the keys and ciphertexts can be built by dynamic subsets of clients. As any encryption scheme, all the FE schemes provide privacy of the plaintexts. But the functions associated to the functional decryption keys might be sensitive too (e.g. a model in machine learning). The function-hiding property has thus been introduced to additionally protect the function evaluated during the decryption process. In this paper, we first provide a generic conversion from DMCFE to DDFE, that preserves the security properties, in both the standard and the function-hiding setting. Then, new proof techniques allow us to analyze a new concrete construction of function-hiding DMCFE for inner products, that can thereafter be converted into a DDFE, with strong security guarantees: the adversary can adaptively query multiple challenge ciphertexts and multiple challenge keys. Previous constructions were proven secure in the selective setting only.
Last updated:  2023-10-11
Faulting Winternitz One-Time Signatures to forge LMS, XMSS, or SPHINCS+ signatures
Alexander Wagner, Vera Wesselkamp, Felix Oberhansl, Marc Schink, and Emanuele Strieder
Hash-based signature (HBS) schemes are an efficient method of guaranteeing the authenticity of data in a post-quantum world. The stateful schemes LMS and XMSS and the stateless scheme SPHINCS+ are already standardised or will be in the near future. The Winternitz one-time signature (WOTS) scheme is one of the fundamental building blocks used in all these HBS standardisation proposals. We present a new fault injection attack targeting WOTS that allows an adversary to forge signatures for arbitrary messages. The attack affects both the signing and verification processes of all current stateful and stateless schemes. Our attack renders the checksum calculation within WOTS useless. A successful fault injection allows at least an existential forgery attack and, in more advanced settings, a universal forgery attack. While checksum computation is clearly a critical point in WOTS, and thus in any of the relevant HBS schemes, its resilience against a fault attack has never been considered. To fill this gap, we theoretically explain the attack, estimate its practicability, and derive the brute-force complexity to achieve signature forgery for a variety of parameter sets. We analyse the reference implementations of LMS, XMSS and SPHINCS+ and pinpoint the vulnerable points. To harden these implementations, we propose countermeasures and evaluate their effectiveness and efficiency. Our work shows that exposed devices running signature generation or verification with any of these three schemes must have countermeasures in place.
Last updated:  2023-10-11
Key Filtering in Cube Attacks from the Implementation Aspect
Hao Fan, Yonglin Hao, Qingju Wang, Xinxin Gong, and Lin Jiao
In cube attacks, key filtering is a basic step of identifying the correct key candidates by referring to the truth tables of superpolies. When terms of superpolies get massive, the truth table lookup complexity of key filtering increases significantly. In this paper, we propose the concept of implementation dependency dividing all cube attacks into two categories: implementation dependent and implementation independent. The implementation dependent cube attacks can only be feasible when the assumption that one encryption oracle query is more complicated than one table lookup holds. On the contrary, implementation independent cube attacks remain feasible in the extreme case where encryption oracles are implemented in the full codebook manner making one encryption query equivalent to one table lookup. From this point of view, we scrutinize existing cube attack results of stream ciphers Trivium, Grain-128AEAD, Acorn and Kreyvium. As a result, many of them turn out to be implementation dependent. Combining with the degree evaluation and divide-and-conquer techniques used for superpoly recovery, we further propose new cube attack results on Kreyvium reduced to 898, 899 and 900 rounds. Such new results not only mount to the maximal number of rounds so far but also are implementation independent.
Last updated:  2023-10-11
Jackpot: Non-Interactive Aggregatable Lotteries
Nils Fleischhacker, Mathias Hall-Andersen, Mark Simkin, and Benedikt Wagner
In proof-of-stake blockchains, liveness is ensured by repeatedly selecting random groups of parties as leaders, who are then in charge of proposing new blocks and driving consensus forward, among all their participants. The lotteries that elect those leaders need to ensure that adversarial parties are not elected disproportionately often and that an adversary can not tell who was elected before those parties decide to speak, as this would potentially allow for denial-of-service attacks. Whenever an elected party speaks, it needs to provide a winning lottery ticket, which proves that the party did indeed win the lottery. Current solutions require all published winning tickets to be stored individually on-chain, which introduces undesirable storage overheads. In this work, we introduce {non-interactive aggregatable lotteries} and show how these can be constructed efficiently. Our lotteries provide the same security guarantees as previous lottery constructions, but additionally allow any third party to take a set of published winning tickets and aggregate them into one short digest. We provide a formal model of our new primitive in the universal composability framework. As one of our main technical contributions, which may be of independent interest, we introduce aggregatable vector commitments with simulation-extractability and present a concretely efficient construction thereof in the algebraic group model in the presence of a random oracle. We show how these commitments can be used to construct non-interactive aggregatable lotteries. We have implemented our construction, called {Jackpot}, and provide benchmarks that underline its concrete efficiency.
Last updated:  2023-10-11
Composable Oblivious Pseudo-Random Functions via Garbled Circuits
Sebastian Faller, Astrid Ottenhues, and Johannes Ottenhues
Oblivious Pseudo-Random Functions (OPRFs) are a central tool for building modern protocols for authentication and distributed computation. For example, OPRFs enable simple login protocols that do not reveal the password to the provider, which helps to mitigate known shortcomings of password-based authentication such as password reuse or mix-up. Reliable treatment of passwords becomes more and more important as we login to a multitude of services with different passwords in our daily life. To ensure the security and privacy of such services in the long term, modern protocols should always consider the possibility of attackers with quantum computers. Therefore, recent research has focused on constructing post-quantum-secure OPRFs. Unfortunately, existing constructions either lack efficiency, or they are based on complex and relatively new cryptographic assumptions, some of which have lately been disproved. In this paper, we revisit the security and the efficiency of the well-known “OPRFs via Garbled Circuits” approach. Such an OPRF is presumably post-quantum-secure and built from well-understood primitives, namely symmetric cryptography and oblivious transfer. We investigate security in the strong Universal Composability model, which guarantees security even when multiple instances are executed in parallel and in conjunction with arbitrary other protocols, which is a realistic scenario in today’s internet. At the same time, it is faster than other current post-quantumsecure OPRFs. Our implementation and benchmarks demonstrate that our proposed OPRF is currently among the best choices if the privacy of the data has to be guaranteed for a long time.
Last updated:  2023-10-11
On the (Im)possibility of Distributed Samplers: Lower Bounds and Party-Dynamic Constructions
Damiano Abram, Maciej Obremski, and Peter Scholl
Distributed samplers, introduced by Abram, Scholl and Yakoubov (Eurocrypt ’22), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the standard model, even with a CRS, the output of the sampling protocol must have low entropy. This essentially implies that this type of construction is useless in applications. Secondly, we study the question of building distributed samplers in the party-dynamic setting, where parties can join in an ad-hoc manner, and the total number of parties is unbounded. Here, we obtain positive results. First, we build a special type of unbounded universal sampler, which after a trusted setup, allows sampling from any distributed with unbounded size. Our construction is in the shared randomness model, where the parties have access to a shared random string, and uses indistinguishability obfuscation and somewhere statistically binding hashing. Next, using our unbounded universal sampler, we construct distributed universal samplers in the party-dynamic setting. Our first construction satisfies one-time selective security in the shared randomness model. Our second construction is reusable and secure against a malicious adversary in the random oracle model. Finally, we show how to use party-dynamic, distributed universal samplers to produce ideal, correlated randomness in the party-dynamic setting, in a single round of interaction.
Last updated:  2023-10-11
Advancing Scalability in Decentralized Storage: A Novel Approach to Proof-of-Replication via Polynomial Evaluation
Giuseppe Ateniese, Foteini Baldimtsi, Matteo Campanelli, Danilo Francati, and Ioanna Karantaidou
Proof-of-Replication (PoRep) plays a pivotal role in decentralized storage networks, serving as a mechanism to verify that provers consistently store retrievable copies of specific data. While PoRep’s utility is unquestionable, its implementation in large-scale systems, such as Filecoin, has been hindered by scalability challenges. Most existing PoRep schemes, such as Fisch’s (Eurocrypt 2019), face an escalating number of challenges and growing computational overhead as the number of stored files increases. This paper introduces a novel PoRep scheme distinctively tailored for expansive decentralized storage networks. At its core, our approach hinges on polynomial evaluation, diverging from the probabilistic checking prevalent in prior works. Remarkably, our design requires only a single challenge, irrespective of the number of files, ensuring both prover’s and verifier’s run-times remain manageable even as file counts soar. Our approach introduces a paradigm shift in PoRep designs, offering a blueprint for highly scalable and efficient decentralized storage solutions.
Last updated:  2023-10-11
Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort
Kai-Min Chung, Mi-Ying (Miryam) Huang, Er-Cheng Tang, and Jiapeng Zhang
Alon et al. (CRYPTO 2021) introduced a multiparty quantum computation protocol that is secure with identifiable abort (MPQC-SWIA). However, their protocol allows only inside MPQC parties to know the identity of malicious players. This becomes problematic when two groups of people disagree and need a third party, like a jury, to verify who the malicious party is. This issue takes on heightened significance in the quantum setting, given that quantum states may exist in only a single copy. Thus, we emphasize the necessity of a protocol with publicly verifiable identifiable abort (PVIA), enabling outside observers with only classical computational power to agree on the identity of the malicious party in case of an abort. However, achieving MPQC with PVIA poses significant challenges due to the no-cloning theorem, and previous works proposed by Mahadev (STOC 2018) and Chung et al. (Eurocrypt 2022) for classical verification of quantum computation fall short. In this paper, we obtain the first MPQC-PVIA protocol assuming post-quantum oblivious transfer and a classical broadcast channel. The core component of our construction is a new authentication primitive called auditable quantum authentication (AQA) that identifies the malicious sender with overwhelming probability. Additionally, we provide the first MPQC protocol with best-of-both-worlds (BoBW) security, which guarantees output delivery with an honest majority and remains secure with abort even if the majority is dishonest. Our best-of-both-worlds MPQC protocol also satisfies PVIA upon abort.
Last updated:  2023-10-11
Subversion-Resilient Public Key Encryption with Practical Watchdogs
Pascal Bemmann, Sebastian Berndt, Rongmao Chen, and Tibor Jager
Restoring the security of maliciously implemented cryptosystems has been widely considered challenging due to the fact that the subverted implementation could arbitrarily deviate from the official specification. Achieving security against adversaries that can arbitrarily subvert implementations seems to inherently require trusted component assumptions and/or architectural properties. At ASIACRYPT 2016, Russell et al. proposed an attractive model where a watchdog is used to test and approve individual components of an implementation before or during deployment. Such a detection-based strategy has been useful for designing various cryptographic schemes that are provably resilient to subversion. We consider Russell et al.'s watchdog model from a practical perspective regarding watchdog efficiency. We find that the asymptotic definitional framework while permitting strong positive theoretical results, does not yet guarantee practical watchdogs due to the fact that the running time of a watchdog is only bounded by an abstract polynomial. Hence, in the worst case, the running time of the watchdog might exceed the running time of the adversary, which seems impractical for most applications. We adopt Russell et al.'s watchdog model to the concrete security setting and design the first subversion-resilient public-key encryption scheme which allows for extremely efficient watchdogs with only linear running time. At the core of our construction is a new variant of a combiner for key encapsulation mechanisms (KEMs) by Giacon et al. (PKC'18). We combine this construction with a new subversion-resilient randomness generator that can also be checked by an efficient watchdog, even in constant time, which could be of independent interest for the design of other subversion-resilient cryptographic schemes. Our work thus shows how to apply Russell et al.'s watchdog model to design subversion-resilient cryptography with efficient watchdogs. We insist that this work does not intend to show that the watchdog model outperforms other defense approaches but to demonstrate that practical watchdogs are practically achievable. This is the full version of a work published at PKC21. We identify a subtle flaw in the proof of the previous version and show it is impossible to achieve CPA security under subversion with the proposed approach. However, the same construction can achieve one-way security under subversion.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.