IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
12 June 2023
Universitat Oberta de Catalunya (UOC), KISON Research group
UOC has a research center, the Internet Interdisciplinary Institute (IN3), specialized in studying the study of the Internet and the effects of the interaction between digital technologies and human activity. Inside this research center there are 10 renowed research groups, one of them is the K-riptography and Information Security for Open Networks (KISON).
KISON is a research group focused on creating technologies for the protection of the security of networks, the information transmitted through them and the privacy of their users. The KISON group research lines focus on the compatibility of the security of decentralized networks (e.g. ad-hoc, P2P or IoT networks) and the protection of information in the Internet (especially multimedia contents) with users' rights to privacy.
We offer a two-year post-doc research position and a three-year PhD student position.
See the details at UOC website.
Closing date for applications:
Contact: Helena Rifà-Pous
More information: https://selection.uoc.edu/web/offersjob/offerdetails.aspx?offerID=90896BA916D3CDFD2D61A6285C121189E58DFA9D755F8FA3E04CC901FF357818
LIP6 (Sorbonne University) and QAT (ENS - CNRS - INRIA)
Closing date for applications:
Contact: Elham Kashefi (ekashefi@gmail.com) Harold Ollivier (harold.ollivier@inria.fr)
More information: https://qat.inria.fr
Ryad Benadjila, Arnaud Ebalard
After some statistics and blackbox keys recovery, it continued by analyzing multiple firmwares for those hardware devices and virtual appliances to unveil the root causes of these collisions. It ended up with keygens to recover RSA keys, ECDSA keys and signatures nonces.
The current article describes our journey understanding Cisco ASA randomness issues through years, leading to CVE-2023-20107 [CVE-2023-20107, CSCvm90511]. More generally, it also provides technical and practical feedback on what can and cannot be done regarding entropy sources in association with DRBGs and other random processing mechanisms.
Zhongfeng Niu, Siwei Sun, Hailun Yan, Qi Wang
Zeyu Liu, Yunhao Wang
In this work, we propose a construction that is not only asymptotically efficient (requiring only $\tilde{O}(n)$ polynomial multiplications for bootstrapping of $n$ LWE ciphertexts) but also concretely efficient. We implement our scheme as a C++ library and show that it takes $< 5$ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ${\sim}6.7$ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.
Yun Li, Yufei Duan, Zhicong Huang, Cheng Hong, Chao Zhang, Yifan Song
In this paper, we design a maliciously secure 3PC protocol that matches the same communication as Araki et al. with comparable concrete efficiency as Furukawa et al. To obtain our result, we manage to apply the distributed zero-knowledge proofs (Boneh et al. Crypto 2019) for verifying computations over $\mathbb{Z}_2$ by using \emph{prime} fields and explore the algebraic structure of prime fields to make the computation of our protocol friendly for native CPU computation.
Experiment results show that our protocol is around $3.5\times$ faster for AES circuits than Boyle et al. We also applied our protocol to the binary part (e.g. comparison and truncation) of secure deep neural network inference, and results show that we could reduce the time cost of achieving malicious security in the binary part by more than $67\%$.
Besides our main contribution, we also find a hidden security issue in many of the current probabilistic truncation protocols, which may be of independent interest.
Emre Karabulut, Aydin Aysu
Michael Raymond, Gillian Evers, Jan Ponti, Diya Krishnan, Xiang Fu
Hoeteck Wee
Sanjam Garg, Aarushi Goel, Abhishek Jain, Guru-Vamsi Policharla, Sruthi Sekar
In this work, we envision a world where consumers with low computational resources can outsource the task of proof generation to a group of untrusted servers in a privacy-preserving manner. The main requirement is that these servers should be able to collectively generate proofs at a faster speed (than the consumer). Towards this goal, we introduce a framework called zk-SNARKs-as-a-service ($\mathsf{zkSaaS}$) for faster computation of zk-SNARKs. Our framework allows for distributing proof computation across multiple servers such that each server is expected to run for a shorter duration than a single prover. Moreover, the privacy of the prover's witness is ensured against any minority of colluding servers.
We design custom protocols in this framework that can be used to obtain faster runtimes for widely used zk-SNARKs, such as Groth16 [EUROCRYPT 2016], Marlin [EUROCRYPT 2020], and Plonk [EPRINT 2019]. We implement proof of concept zkSaaS for the Groth16 and Plonk provers. In comparison to generating these proofs on commodity hardware, we show that not only can we generate proofs for a larger number of constraints (without memory exhaustion), but can also get $\approx 22\times$ speed-up when run with 128 parties for $2^{25}$ constraints with Groth16 and $2^{21}$ gates with Plonk.
Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen
Our main result is showing that QPRGs can be constructed assuming the existence of logarithmic-length quantum pseudorandom states. This raises the possibility of basing QPRGs on assumptions weaker than one-way functions. We also consider quantum pseudorandom functions (QPRFs) and show that QPRFs can be based on the existence of logarithmic-length pseudorandom function-like states.
Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.
Alexander Bienstock, Sarvar Patel, Joon Young Seo, Kevin Yeo
Using $\mathsf{RB\text{-}OKVS}$, we obtain state-of-the-art protocols for private set intersection (PSI) and union (PSU). Our semi-honest PSI has up to 12% smaller communication and 13% reductions in monetary cost with slightly larger computation. We also obtain similar improvements for both malicious and circuit PSI. For PSU, our protocol obtains improvements of up to 22% in communication, 40% in computation and 21% in monetary cost. In general, we obtain the most communication- and cost-efficient protocols for all the above primitives.
Finally, we present the first connection between OKVS and volume-hiding encrypted multi-maps (VH-EMM) where the goal is to outsource storage of multi-maps while hiding the number of values associated with each key (i.e., volume). We present $\mathsf{RB\text{-}MM}$ with 16% smaller storage, 5x faster queries and 8x faster setup than prior works.
Arka Rai Choudhuri, Sanjam Garg, Aarushi Goel, Sruthi Sekar, Rohit Sinha
As an example, consider the zkRollup circuit. This circuit involves executing one of $n$ code segments $k$ times. For this case, using $\mathcal{P}\mathfrak{lon}\mathcal{K}$ involves proving a circuit of size $n\cdot k$ code segments. In $\mathcal{S}\mathfrak{ublon}\mathcal{K}$, the prover costs are close to proving a $\mathcal{P}\mathfrak{lon}\mathcal{K}$ proof for a circuit of size roughly $k$ code segments. Concretely, based on our implementation, for parameter choices derived from rollup contracts on Ethereum, $n =8, k = \{2^{10}\ldots 2^{16}\}$, the $\mathcal{S}\mathfrak{ublon}\mathcal{K}$ prover is approximately $4.6\times$ faster than the $\mathcal{P}\mathfrak{lon}\mathcal{K}$ prover. Proofs in $\mathcal{S}\mathfrak{ublon}\mathcal{K}$ are 2.4KB, and can be verified in under 50ms.
Aarushi Goel, Mathias Hall-Andersen, Aditya Hegde, Abhishek Jain
While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To alleviate this, a series of recent works have investigated the problem of reducing the communication cost of branching executions inside MPC (without relying on fully homomorphic encryption). Most notably, the stacked garbling paradigm [Heath and Kolesnikov, CRYPTO'20] yields garbled circuits for branching circuits whose size only depends on the size of the largest branch. Presently, however, it is not known how to obtain similar communication improvements for secure computation involving more than two parties.
In this work, we provide a generic framework for branching multi-party computation that supports any number of parties. The communication complexity of our scheme is proportional to the size of the largest branch and the computation is linear in the size of the entire circuit. We provide an implementation and benchmarks to demonstrate practicality of our approach.
Anindya Bhandari, Allison Bishop
Hien Chu, Paul Gerhart, Tim Ruffing, Dominique Schröder
We continue this line of research by focusing on FROST's unforgeability combined with a practical distributed key generation (DKG) algorithm. Existing proofs of this setup either use non-standard heuristics, idealized group models like the AGM, or idealized key generation. Moreover, existing proofs do not consider all practical relevant optimizations that have been proposed. We close this gap between theory and practice by presenting the Schnorr threshold signature scheme Olaf, which combines the most efficient known FROST variant FROST3 with a variant of Pedersen's DKG protocol (as commonly used for FROST), and prove its unforgeability. Our proof relies on the AOMDL assumption (a weaker and falsifiable variant of the OMDL assumption) and, like proofs of regular Schnorr signatures, on the random oracle model.
Céline Chevalier, Guirec Lebrun, Ange Martinelli
Regarding the hybridization of Key Encapsulation Mechanisms (KEMs), most recent studies focus on how to safely combine the symmetric keys output by a parallel execution of classical and post-quantum KEMs. As simple as this architecture is, it however appears not to be the most efficient, computationally speaking as well as regarding the bandwidth of the exchanges.
Hence, we propose a new method to hybridize several KEMs more effectively, by combining the underlying Public Key Encryption schemes (PKEs) in an innovative variant of the cas- cade composition that we call "leaking-cascade". We prove that this architecture constitutes an IND-CPA-secure robust combiner for the encryption schemes, which permits to create an IND-CCA2 KEM upon the generated hybrid PKE. The leaking-cascade is at least as computationally effective as the commonly used parallel combination, and has a bandwidth gain - when it comes to the ciphertext produced - that may exceed 13 % compared to the latter.
Emanuele Giunta
As of today no construction is known to simultaneously reduce its security to pairing-free group problems and to use the underlying group in a black-box way.
This is indeed not a coincidence: in this paper, we prove that for a large class of NIZK either a pairing-free group is used non black-box by relying on element representation, or security reduces to external hardness assumptions. More specifically our impossibility applies to two incomparable cases. The first one covers Arguments of Knowledge (AoK) which proves that a preimage under a given one way function is known. The second one covers NIZK (not necessarily AoK) for hard subset problems, which captures relations such as DDH, Decision-Linear and Matrix-DDH.
Jean-Sébastien Coron, François Gérard, Matthias Trannoy, Rina Zeitoun
We demonstrate the effectiveness of our countermeasures by presenting a complete high-order masked implementation of Dilithium that utilizes the improved gadgets described above. We provide practical results obtained from a C implementation and compare the performance improvements provided by our new gadgets with those of previous work.
Anisha Mukherjee, Aikata Aikata, Ahmet Can Mert, Yongwoo Lee, Sunmin Kwon, Maxim Deryabin, Sujoy Sinha Roy
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.