IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
15 August 2023
Kosei Sakamoto, Ryoma Ito, Takanori Isobe
ePrint ReportHuayi Qi, Minghui Xu, Dongxiao Yu, Xiuzhen Cheng
ePrint ReportYuval Ishai, Mahimna Kelkar, Varun Narayanan, Liav Zafar
ePrint ReportDifferent kinds of correlations can vary greatly in terms of usefulness and ease of generation. While there has been major progress on efficiently generating oblivious transfer (OT) correlations, other useful kinds of correlations are much more costly to generate. Thus, it is highly desirable to develop efficient techniques for securely converting copies of a given source correlation into copies of a given target correlation, especially when the former are cheaper to generate than the latter.
In this work, we initiate a systematic study of such conversions that only involve a single uni-directional message. We refer to such a conversion as a one-message secure reduction (OMSR). Recent works (Agarwal et al, Eurocrypt 2022; Khorasgani et al, Eurocrypt 2022) studied a similar problem when no communication is allowed; this setting is quite restrictive, however, with few non-trivial conversions being feasible. The OMSR setting substantially expands the scope of feasible results, allowing for direct applications to existing MPC protocols.
We obtain the following positive and negative results. - OMSR constructions. We present a general rejection-sampling based technique for OMSR with OT source correlations. We apply it to substantially improve in the communication complexity of optimized protocols for distributed symmetric cryptography (Dinur et al., Crypto 2021).
- OMSR lower bounds. We develop general techniques for proving lower bounds on the communication complexity of OMSR, matching our positive results up to small constant factors.
Kirill Vedenev, Yury Kosolapov
ePrint ReportJohannes Mono, Kamil Kluczniak, Tim Güneysu
ePrint ReportMore specifically, we significantly simplify the bootstrapping idea by Carpov, Izabach`ene, and Mollimard [1] for Boolean-based FHE schemes such as FHEW or TFHE, making the concept usable in practice. Based on our simplifications, we provide an easy-to-use interface for amortized bootstrapping implementing our improvements in the open-source library FHE-Deck and provide new parameter sets for multi-bit encryptions with state-of-the-art security.
We build a toolset that compiles high-level code such as C++ to code that executes operations on encrypted data. For this toolset, we propose the first non-trivial FHE-specific optimizations in synthesizing privacy-preserving circuits from high-level code, namely look-up table (LUT) grouping and adder substitution. Using LUT grouping, we reduce the number of bootstrapping required by almost 35 % on average, while for adder substitution, we reduce the number of required bootstrapping by up to 80 % for certain use cases. Overall, the execution time is up to 3.8× faster using our optimizations compared to previous state-of-the-art circuit synthesis.
Zhipeng Wang, Marko Cirkovic, Duc V. Le, William Knottenbelt, Christian Cachin
ePrint ReportIn this work, we introduce the Merkle Pyramid Builder approach, to incrementally build the Merkle tree in an on-chain mixer and update the tree per batch of deposits, which can therefore decrease the overall cost of using the mixer. Our evaluation results highlight the effectiveness of this approach, showcasing a significant reduction of up to $7\times$ in the amortized cost of depositing compared to state-of-the-art on-chain mixers. Importantly, these improvements are achieved without compromising users' privacy. Furthermore, we propose the utilization of verifiable computations to shift the responsibility of Merkle tree updates from on-chain smart contracts to off-chain clients, which can further reduce deposit costs. Additionally, our analysis demonstrates that our designs ensure fairness by distributing Merkle tree update costs among clients over time.
Mario Mastriani
ePrint Report14 August 2023
Election
Nominations are due by October 1st, 2023.
Information about nomination is available at https://iacr.org/elections/2023/announcement.html.
Department of Information Security and Communication Technology at NTNU in Trondheim, Norway
Job PostingThe NIST Post Quantum Cryptography Standardization is expected to end in 2024, and post-quantum cryptography will be required to secure all sensitive information in the years to come shortly after, e.g., in protocols such as TLS, SSH, FIDO and other systems. Additionally, NIST have announces a new call for quantum secure digital signature algorithms.
This project aims to conduct research on lightweight post-quantum protocols and primitives, including symmetric key primitives, and improve upon the frameworks used today regarding communication size, computation complexity and secure and efficient implementation of long-term security cryptographic primitives.
The postdoc will be part of the NTNU Applied Cryptology Lab, a multidisciplinary research group consisting of members from the Department of Information Security and Communication Technology and the Department of Mathematical Sciences at NTNU.
A list of possible, but not limited to, post-quantum cryptography research topics for the postdoctoral position are:
Your hosts will be Professor Danilo Gligoroski, Professor Stig Frode Mjølsnes, and/or Associate Professor Tjerand Silde.
Closing date for applications:
Contact: Associate Professor Tjerand Silde (tjerand.silde@ntnu.no)
More information: https://www.jobbnorge.no/en/available-jobs/job/248833/postdoctoral-fellow-in-lightweight-post-quantum-cryptography
IT University of Copenhagen (ITU)
Job PostingWe are hiring a PhD student to work on a project investigating privacy preserving yet auditable cryptographic protocols for decentralized applications. The student will be working in one (or more) of the following areas: secure multiparty computation, zero knowledge, anonymous credentials, blockchain consensus, cryptocurrencies, differential privacy.
The ideal candidate should have a background in computer science or mathematics, with a focus on complexity theory, number theory, algebra and probability theory. Previous research experience in security and cryptography (specially in cryptographic protocols) is most welcome. Moreover, the candidate should be motivated and enthusiastic about theoretical research in cryptography.
ITU is located in beautiful Copenhagen, which is well connected by flight to many locations. We offer a competitive salary following Danish standards as well as travel funding for scientific visits and events. As a resident in Denmark, the student will also have access to the excellent public education and health systems.
Candidates are welcome to contact Bernardo David by email for any questions. Notice, however, that all applications must be submitted via the official URL.
Closing date for applications:
Contact: Bernardo David (beda@itu.dk)
More information: https://candidate.hr-manager.net/ApplicationInit.aspx?cid=119&ProjectId=181605&DepartmentId=3439&MediaId=5
IDEAS NCBR
Job PostingClosing date for applications:
Contact: Marta Krzyżycka
More information: https://ideas-ncbr.softgarden.io/job/34064687?l=pl
Quantum-Safe Migration Center, Chelpis Quantum Tech, Taipei, Taiwan
Job PostingChelpis Quantum Tech was established in 2017, drawing its team from the Fast Cryptography Laboratory at National Taiwan University. Our primary focus has been research and development of post-quantum cryptographic systems and the creation of related cryptographic applications.
QSMC is looking for an applied post-quantum cryptography researcher to join our research team in Taipei, Taiwan.
We currently have three research focus areas and candidates should be experienced in at least one:
- PQC Hardware
- Formally-verified PQC Software
- New PQC primitives (in particular, candidates of the recent NIST PQC digital signature competition)
- Work on research projects and publish at top-tier cryptography and security conferences
- Collaborate with researchers in Taiwan and internationally
- Present research on international workshops and conferences
- Contribute to standardization efforts such as NIST PQC
- Consult Chelpis' other teams in all aspects of post-quantum cryptography
Closing date for applications:
Contact:
- Ming Chih (my.chih@chelpis.com)
- Matthias Kannwischer (matthias@chelpis.com)
More information: https://www.qsmc.org/
National Research Council Canada
Job PostingClosing date for applications:
Contact: https://recruitment-recrutement.nrc-cnrc.gc.ca/job/Various-Locations-Applied-Cryptography-Research-Officer-ON/572782617/
More information: https://recruitment-recrutement.nrc-cnrc.gc.ca/job/Various-Locations-Applied-Cryptography-Research-Officer-ON/572782617/
11 August 2023
Pierre-Augustin BERTHET, Cédric Tavernier, Jean-Luc Danger, Laurent Sauvage
ePrint ReportMarcel Keller, Ke Sun
ePrint ReportNicolas Mohnblatt, Alberto Sonnino, Kobi Gurkan, Philipp Jovanovic
ePrint ReportArasu Arun, Srinath Setty, Justin Thaler
ePrint ReportA $\textit{front-end}$ converts computer programs into a lower-level representation such as an arithmetic circuit or generalization thereof. A SNARK for circuit-satisfiability can then be applied to the resulting circuit.
We describe a new front-end technique called Jolt that applies to a variety of ISAs. Jolt arguably realizes a vision called the $\textit{lookup singularity}$, which seeks to produce circuits that only perform lookups into pre-determined lookup tables. The circuits output by Jolt primarily perform lookups into a gigantic lookup table, of size more than $2^{128}$, that depends only on the ISA. The validity of the lookups are proved via a new $\textit{lookup argument}$ called Lasso described in a companion work (Setty, Thaler, and Wahby, e-print 2023). Although size-$2^{128}$ tables are vastly too large to materialize in full, the tables arising in Jolt are structured, avoiding costs that grow linearly with the table size.
We describe performance and auditability benefits of Jolt compared to prior zkVMs, focusing on the popular RISC-V ISA as a concrete example. The dominant cost for the Jolt prover applied to this ISA (on $64$-bit data types) is cryptographically committing to about six $256$-bit field elements per step of the RISC-V CPU. This compares favorably to prior zkVM provers, even those focused on far simpler VMs.
Srinath Setty, Justin Thaler, Riad Wahby
ePrint ReportFor $m$ lookups into a table of size $n$, Lasso’s prover commits to just $m + n$ field elements. Moreover, the committed field elements are small, meaning that, no matter how big the field $\mathbb{F}$ is, they are all in the set $\{0, . . . , m\}$. When using a multiexponentiation-based commitment scheme, this results in the prover’s costs dominated by only $O(m + n)$ group operations (e.g., elliptic curve point additions), plus the cost to prove an evaluation of a multilinear polynomial whose evaluations over the Boolean hypercube are the table entries. This represents a significant improvement in prover costs over prior lookup arguments (e.g., plookup, Halo2’s lookups, lookup arguments based on logarithmic derivatives).
Unlike all prior lookup arguments, if the table $t$ is structured (in a precise sense that we define), then no party needs to commit to $t$, enabling the use of much larger tables than prior works (e.g., of size $2^{128}$ or larger). Moreover, Lasso’s prover only "pays" in runtime for table entries that are accessed by the lookup operations. This applies to tables commonly used to implement range checks, bitwise operations, big-number arithmetic, and even transitions of a full-fledged CPU such as RISC-V. Specifically, for any integer parameter $c > 1$, Lasso’s prover’s dominant cost is committing to $3 \cdot c \cdot m + c \cdot n^{1/c}$ field elements. Furthermore, all these field elements are “small”, meaning they are in the set $\{0, . . . , \max{(m, n^{1/c}, q)} − 1\}$, where $q$ is the maximum value in $a$.
Lasso’s starting point is Spark, a time-optimal polynomial commitment scheme for sparse polynomials in Spartan (CRYPTO 2020). We first provide a stronger security analysis for Spark. Spartan’s security analysis assumed that certain metadata associated with a sparse polynomial is committed by an honest party (this is acceptable for its purpose in Spartan, but not for Lasso). We prove that Spark remains secure even when that metadata is committed by a malicious party. This provides the first "standard" commitment scheme for sparse multilinear polynomials with optimal prover costs. We then generalize Spark to directly support a lookup argument for both structured and unstructured tables, with the efficiency characteristics noted above.
Ripon Patgiri, Laiphrakpam Dolendro Singh
ePrint ReportMarc Fischlin, Felix Günther
ePrint ReportWe propose here a mechanism which supports the detection of such errors on a cryptographic level. Instead of merely returning the binary acceptance decision, we let the verification return more fine-grained information in form of what we call a confirmation code. The reader may think of the confirmation code as disposable information produced as part of the relevant verification steps. In case of an implementation error like the goto fail bug, the confirmation code would then miss essential elements.
The question arises now how to verify the confirmation code itself. We show how to use confirmation codes to tie security to basic functionality at the overall protocol level, making erroneous implementations be detected through the protocol not functioning properly. More concretely, we discuss the usage of confirmation codes in secure connections, established via a key exchange protocol and secured through the derived keys. If some verification steps in a key exchange protocol execution are faulty, then so will be the confirmation codes, and because we can let the confirmation codes enter key derivation, the connection of the two parties will eventually fail. In consequence, an implementation error like goto fail would now be detectable through a simple connection test.