International Association for Cryptologic Research

International Association
for Cryptologic Research


Updates on the COVID-19 situation are on the Announcement channel.

Here you can see all recent updates to the IACR webpage. These updates are also available:

email icon
via email
RSS symbol icon
via RSS feed
Twitter bird icon
via Twitter
Weibo icon
via Weibo
Facebook icon
via Facebook

23 June 2022

Ittai Abraham, Danny Dolev, Alon Kagan, Gilad Stern
ePrint Report ePrint Report
Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if $n>2f$ for $f$ Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if $n>3f+2k$ for $f$ Byzantine faults and $k$ crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to $f$ Byzantine faults and $k$ crash faults if $n>2f+k$. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that $n>2f+k$ is optimally resilient for consensus and state machine replication protocols.
Alex Charlès, Chloé Gravouil
ePrint Report ePrint Report
One of the main challenges cryptography needs to deal with is balancing the performances of a cryptographic primitive with its security. That is why in 2015, the National Institute of Standards and Technologies (NIST) has begun a standardization process to solicit the creation of new lightweight cryptographic algorithms. We then wondered which of this standardization finalists would suit the best to a white-box implementation. To this end, we studied different algorithms structures on their encodability to later develop our white-box encoding solution. Afterwards, we reviewed the standardization finalists on the applicability of our solution to those algorithms, and finally apply it to GIFT, the permutation of GIFT-COFB.
Xavier Arnal, Tamara Finogina, Javier Herranz
ePrint Report ePrint Report
Interactive zero-knowledge systems are a very important cryptographic primitive, used in many applications, especially when non-transferability is desired. In the setting of lattice-based cryptography, the currently most efficient interactive zero-knowledge systems employ the technique of rejection sampling, which implies that the interaction does not always finish correctly in the first execution; the whole interaction must be re-run until abort does not happen.

While aborts and repetitions are acceptable in theory, in some practical applications of such interactive systems it is desirable to avoid re-runs, for usability reasons. In this work, we present a generic transformation that departs from an interactive zero-knowledge system (maybe with aborts) and obtains a 3-moves zero-knowledge system (without aborts). The transformation combines the well-known Fiat-Shamir technique with a couple of initially exchanged messages. %, needed to get the (honest-verifier) zero-knowledge property. The resulting 3-moves system enjoys (honest-verifier) zero-knowledge and soundness, in the random oracle model. We finish the work by showing some practical scenarios where our transformation can be useful.
Alex Luoyuan Xiong, Binyi Chen, Zhenfei Zhang, Benedikt Bünz, Ben Fisch, Fernando Krell, Philippe Camacho
ePrint Report ePrint Report
Traditional blockchain systems execute program state transitions on-chain, requiring each network node participating in state-machine replication to re-compute every step of the program when validating transactions. This limits both scalability and privacy. Recently, Bowe et al. introduced a primitive called decentralized private computation (DPC) and provided an instantiation called ZEXE, which allows users to execute arbitrary computations off-chain without revealing the program logic to the network. Moreover, transaction validation takes only constant time, independent of the off-chain computation. However, ZEXE required a separate trusted setup for each application, which is highly impractical. Prior attempts to remove this per-application setup incurred significant performance loss. We propose a new DPC instantiation VERI-ZEXE that is highly efficient and requires only a single universal setup to support an arbitrary number of applications. Our benchmark improves the state-of-the-art by 9x in transaction generation time and by 2.6x in memory usage. Along the way, we also design efficient gadgets for variable-base multi-scalar multiplication and modular arithmetic within the plonk constraint system, leading to a Plonk verifier gadget using only ∼ 21k plonk constraints.
Hadi Mardani Kamali
ePrint Report ePrint Report
Having access to the scan chain of Integrated Circuits (ICs) is an integral requirement of the debug/testability process within the supply chain. However, the access to the scan chain raises big concerns regarding the security of the chip, particularly when the secret information, such as the key of logic obfuscation, is embedded/stored inside the chip. Hence, to relieve such concerns, numerous secure scan chain architectures have been proposed in the literature to show not only how to prevent any unauthorized access to the scan chain but also how to keep the availability of the scan chain for debug/testability. In this paper, we first provide a holistic overview of all secure scan chain architectures. Then, we discuss the key leakage possibility and some substantial architectural drawbacks that moderately affect both test flow and design constraints in the state-of-the-art published design-for-security (DFS) architectures. Then, we propose a new key-trapped DFS (kt-DFS) architecture for building a secure scan chain architecture while addressing the potential of key leakage. The proposed kt-DFS architecture allows the designer to perform the structural test with no limitation, enabling an untrusted foundry to utilize the scan chain for manufacturing fault testing without needing to access the scan chain. Finally, we evaluate and compare the proposed architecture with state-of-the-art ones in terms of security, testability time and complexity, and area/power/delay overhead.
Sameer Wagh
ePrint Report ePrint Report
Recent advances in function secret sharing (FSS) have led to new possibilities in multi-party computation in the pre-processing model. Silent Pseudorandom Correlation Generators (Crypto '19, CCS '19, CCS '19, CCS '20) have demonstrated the ability to generate large quantities of pre-processing material such as oblivious transfers and Beaver triples through a non-interactive offline phase (with an initial set-up). However, there has been limited protocols for pre-processing material such as doubly authenticated bits (daBits, IndoCrypt'19) and extended doubly authenticated bits (edaBits, Crypto '20) which are critical for state-of-the-art secure comparison protocols over arithmetic secret sharing.

In this work, we propose new protocols in a 3-party computation model for these two cryptographic primitives -- daBits and edaBits. We explore how advances in silent PCGs can be used to construct efficient protocols for daBits and edaBits. Our protocols are secure against a single corruption in both the semi-honest and malicious security models. Our contributions can be summarized as follows:

(1) New constant round protocols for generating daBits and edaBits. We achieve this by constructing an efficient 3-party oblivious transfer protocol (using just 2 rounds of computation) and using it to build efficient protocols for daBit and edaBit generation. (2) We extend the above semi-honest protocol to achieve malicious security against an honest majority. We use a standard cut-and-choose approach for this. This improves the round complexity of prior edaBit protocols from O(log2 l) to a constant, where l is the bit-length of the inputs. (3) Finally, to understand when the above protocols provide concrete efficiency, we implement and benchmark the performance of our protocols against state-of-the-art implementation of these primitives in MP-SDPZ. Our protocols improve the throughput of daBit generation by up to 10x in the LAN setting and 5x in the WAN setting. Comparing the performance of edaBit generation, our protocols achieve 4x higher throughput in the LAN setting and 32x higher throughput in the WAN setting.

It is known that silent PCGs are compute intense and thus the performance of these new protocols can further be improved using works such as CryptGPU (S\&P '21), Piranha (USENIX '22) that significantly improve the local computation in MPC protocols.

22 June 2022

Trento, Italia, 10 October - 14 October 2022
Event Calendar Event Calendar
Event date: 10 October to 14 October 2022
Submission deadline: 19 August 2022
Notification: 9 September 2022
Pandit Deendayal Energy University, Gandhinagar, Guarat, India
Job Posting Job Posting
Pandit Deendayal Energy University is looking for meritorious young researchers for the post of Junior Research Fellow (01 Post) on a Supporting R&D in Emerging Fields of S&T on state priority areas under STI fund, sponsored project grant by Gujarat Council on Science and Technology ( GUJCOST) under Department of Science & Technology. The details are given below.
Project Title: Developing a Privacy Preserving Framework for Securing Organizational Data Publication
Duration: 2022-25
PI: Dr. Payal Chaudhari, Assistant Professor, Department of Computer Science and Engineering, Pandit Deendayal Energy University, Gandhinagar, Gujarat, India
Co-PI: Dr. Nishant Doshi, Associate Professor, Department of Computer Science and Engineering, Pandit Deendayal Energy University, Gandhinagar, Gujarat, India
Essential Qualification: M.E./M.Tech in Computer Science & Engg./Computer Engg./Information Technology / Information and Communication Technology or equivalent
Additional Skills : Experimental exposure to cloud set-up and Infrastructure. Knowledge of and interest in Cryptography applications. Knowledge of Network Security Tools will be an added advantage.
Fellowship: As per funding agency norms.

Closing date for applications:

Contact: Dr. Payal Chaudhari

More information:

Graz University of Technology
Job Posting Job Posting
Graz University of Technology actively promotes diversity and equal opportunities. Applicants are not to be placed at a disadvantage in personnel selection procedures on the grounds of criteria such as age, gender, ethnicity, religion or ideology, sexual orientation or special needs due to a disability. We aim to increase the proportion of women, in particular in management and academic staff, and therefore particularly encourages qualified women to apply. In the event of under-representation, women with equal qualifications will be given priority.

We are looking for a full-time PhD researcher who will work on cryptographic hardware and software implementations. The researcher will be supervised by Dr. Sujoy Sinha Roy at IAIK, Graz University of Technology, Austria.

The Institute of Applied Information Processing and Communications (aka IAIK) is the largest university institute in Austria for research and education in security and privacy. It has been active in this field for more than 30 years and currently employs more than 60 researchers.

The PhD researcher will be working on Scientific research in the field of implementation and physical security aspects of novel cryptographic algorithms in the “Cryptographic Engineering” group within the “Secure Systems” area at IAIK.

Required Qualifications:
  • MSc degree in computer science, information and computer engineering, electrical or electronics engineering, mathematics, or a related field.
  • BSc students with excellent academic records and project experience are also encouraged.
  • Excellent knowledge of English
  • The ability to work in an international environment
  • Research experience from projects or publication of scientific papers
  • Excellent skills in programming and/or digital circuit design

    Please submit your application online:

    Closing date for applications:

    Contact: If you have any specific questions about the application please contact Sujoy Sinha Roy directly:

    More information:

  • Expand
    University of Houston Downtown
    Job Posting Job Posting
    The Department of Computer Science and Engineering Technology at the University of Houston–Downtown (UHD) invites applications for multiple tenure-track faculty positions in Computer Science. Depending on the applicant's qualifications, the position can be at Assistant or Associate Professor level. We are looking for outstanding candidates with expertise in area of Artificial Intelligence (AI), Machine Learning or Cybersecurity. The appointment will start in January 2023. Candidates will be expected to teach at the undergraduate and graduate levels, establish an externally funded research program and provide service and leadership to the campus and the scientific community. UHD values diversity, equity and inclusion and is committed to hiring faculty who share these values. To be considered, candidates must describe their experience and future plans to promote equity and inclusion in teaching, mentoring and research. Financial and in-kind resources will be made available to faculty who promote equity and inclusion at UHD, and their work will be recognized as important university service during the faculty promotion process.

    Closing date for applications:


    More information:


    21 June 2022

    Award Award
    Award for Excellence in the Field of Mathematics, Co-Sponsored by IACR

    Each year, RSA Conference recognizes noteworthy work in cryptography and mathematics. Award recipients are determined by an esteemed judging committee who seek to recognize innovation and ongoing contributions to the industry. Dozens of nominated individuals from affiliated organizations, universities or research labs compete each year for this award.

    Recipients of the RSA Conference 2022 Excellence in the Field of Mathematics award are:

    Professors Cynthia Dwork and Moni Naor
    Cynthia Dwork, a professor of Computer Science at the John A. Paulson School of Engineering and Applied Sciences at Harvard University and a Distinguished Scientist at Microsoft Research, is known for establishing the pillars on which every fault-tolerant system has been built atop for decades. Her innovations modernized cryptography to cope with the ungoverned interactions of the internet through the development of non-malleable cryptography, formed the basis of crypto currencies through proofs of work, placed privacy-preserving data analysis on a firm mathematical foundation, and ensures statistical validity in exploratory data analysis, through differential privacy.

    "RSA Conference is an important venue for the exchange of ideas in the cybersecurity ecosystem. I am deeply honored to join the ranks of past recipients of this prestigious award that recognizes foundational research," said Dwork. "The threats to privacy have never been greater, and advancements in technology means more cybersecurity risk. My research, work, students, and university will continue to play a key role in helping innovation preserve these values."

    Moni Naor is a professor of Computer Science at the Weizmann Institute of Science in Israel specializing in Cryptography and Complexity. He is well known for his work connecting cryptography and data structure in adversarial environments. In 1992, he collaborated with Cynthia Dwork on "Proofs of Work" to combat denial-of-service attacks and other service abuses, such as spam, which is now famous for its use with Bitcoin and blockchain technologies. He has proposed other fundamental concepts that are at the heart of today's cryptography, including non-malleability, broadcast encryption, tracing traitors, small bias probability, and the efficiency of falsifying assumptions.

    "The RSA Conference Excellence in the Field of Mathematics Awards has a long list of impressive and impactful recipients dating back to 1998 with Shafi Goldwasser receiving it. I am honored to say that I am now part of the amazing group of cryptographers who have received it," said Naor. "I strongly believe advancements in the field of cryptography will continue to prove necessary as digital communication and usage accelerates. I remain dedicated to making a lasting impact in the field."

    “The IACR is proud to join RSAC in co-sponsoring the Excellence in the Field of Mathematics Award. As the worldwide professional society for researchers in cryptography and cryptanalysis, we are dedicated to recognizing individuals who have excelled in our field and advancing awareness of the role cryptology plays in a modern, digitally connected life,” said Michel Abdalla, President, IACR. “This year we celebrate the work of Professors Dwork and Naor, and the impact they individually and collectively have had on the cryptography industry and cybersecurity at large.”

    RSA Conference and IACR presented the Excellence Award in the Field of Mathematics Award on Tuesday, June 7, 2022.
    Vipul Goyal, Yuval Ishai, Yifan Song
    ePrint Report ePrint Report
    We revisit the question of minimizing the randomness complexity of protocols for secure multiparty computation (MPC) in the setting of perfect information-theoretic security. Kushilevitz and Mansour (SIAM J. Discret. Math., 1997) studied the case of $n$-party semi-honest MPC for the XOR function with security threshold $t
    We essentially close the question by proving an $\Omega(t^2)$ lower bound on the randomness complexity of XOR, matching the previous upper bound up to a logarithmic factor (or constant factor when $t=\Omega(n)$). We also obtain an explicit protocol that uses $O(t^2\cdot\log^2n)$ random bits, matching our lower bound up to a polylogarithmic factor. We extend these results from XOR to general symmetric Boolean functions and to addition over a finite Abelian group, showing how to amortize the randomness complexity over multiple additions.

    Finally, combining our techniques with recent randomness-efficient constructions of private circuits, we obtain an explicit protocol for evaluating a general circuit $C$ using only $O(t^2\cdot\log |C|)$ random bits, by employing additional ``helper parties'' who do not contribute any inputs. This upper bound too matches our lower bound up to a logarithmic factor.
    David Heath, Vladimir Kolesnikov
    ePrint Report ePrint Report
    Garbled Circuit (GC) is the main practical 2PC technique, yet despite great interest in its performance, GC notoriously resists improvement. Essentially, we only know how to evaluate GC functions gate-by-gate using encrypted truth tables; given input labels, the GC evaluator decrypts the corresponding output label.

    Interactive protocols enjoy more sophisticated techniques. For example, we can expose to a party a (masked) private value. The party can then perform useful local computation and feed the resulting cleartext value back into the MPC. Such techniques are not known to work for GC.

    We show that it is, in fact, possible to improve GC efficiency, while keeping its round complexity, by exposing masked private values to the evaluator. Our improvements use garbled one-hot encodings of values. By using this encoding we improve a number of interesting functions, e.g., matrix multiplication, integer multiplication, field element multiplication, field inverses and AES S-Boxes, integer exponents, and more. We systematize our approach by providing a framework for designing such GC modules.

    Our constructions are concretely efficient. E.g., we improve binary matrix multiplication inside GC by more than $6\times$ in terms of communication and by more than $4\times$ in terms of WAN wall-clock time.

    Our improvement circumvents an important GC lower bound and may open GC to further improvement.

    20 June 2022

    Abida Haque, David Heath, Vladimir Kolesnikov, Steve Lu, Rafail Ostrovsky, Akash Shah
    ePrint Report ePrint Report
    Arecentlineofwork, Stacked Garbled Circuit(SGC), showed that Garbled Circuit (GC) can be improved for functions that include conditional behavior. SGC relieves the communication bottleneck of 2PC by only sending enough garbled material for a single branch out of the b total branches. Hence, communication is sublinear in the circuit size. However, both the evaluator and the generator pay in computation and perform at least factor $\log b$ extra work as compared to standard GC.

    We extend the sublinearity of SGC to also include the work performed by the GC evaluator E; thus we achieve a fully sublinear E, which is essential when optimizing for the online phase. We formalize our approach as a garbling scheme called GCWise: GC WIth Sublinear Evaluator.

    We show one attractive and immediate application, Garbled PIR, a primitive that marries GC with Private Information Retrieval. Garbled PIR allows the GC to non-interactively and sublinearly access a privately indexed element from a publicly known database, and then use this element in continued GC evaluation.
    Youer Pu, Lorenzo Alvisi, Ittay Eyal
    ePrint Report ePrint Report
    Nakamoto's consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? This paper shows that, at least in a benign failure model, it is not. It presents Sandglass, the first permissionless consensus algorithm that guarantees deterministic agreement and termination with probability 1 under general omission failures. Like Nakamoto, Sandglass adopts a hybrid synchronous communication model, where, at all times, a majority of nodes (though their number is unknown) are correct and synchronously connected, and allows nodes to join and leave at any time.
    David Heath, Vladimir Kolesnikov, Jiahui Lu
    ePrint Report ePrint Report
    Katz et al., CCS 2018 (KKW) is a popular and efficient MPC-in-the-head non-interactive ZKP (NIZK) scheme, which is the technical core of the post-quantum signature scheme Picnic, currently considered for standardization by NIST. The KKW approach simultaneously is concretely efficient, even on commodity hardware, and does not rely on trusted setup. Importantly, the approach scales linearly in the circuit size with low constants with respect to proof generation time, proof verification time, proof size, and RAM consumption. However, KKW works with Boolean circuits only and hence incurs significant cost for circuits that include arithmetic operations.

    In this work, we extend KKW with a suite of efficient arithmetic operations over arbitrary rings and Boolean conversions. Rings $\mathbb{Z}_{2^k}$ are important for NIZK as they naturally match the basic operations of modern programs and CPUs. In particular, we: * present a suitable ring representation consistent with KKW, * construct efficient conversion operators that translate between arith- metic and Boolean representations, and * demonstrate how to efficiently operate over the arithmetic representation, including a vector dot product of length-n vectors with cost equal to that of a single multiplication. These improvements substantially improve KKW for circuits with arithmetic. As one example, we can multiply 100 × 100 square matrices of 32-bit numbers using a 3200x smaller proof size than standard KKW (100x improvement from our dot product construction and 32x from moving to an arithmetic representation).

    We discuss in detail proof size and resource consumption and argue the practicality of running large proofs on commodity hardware.
    Dmitrii Koshelev
    ePrint Report ePrint Report
    This article develops a novel method of generating ``independent'' points on an ordinary elliptic curve $E$ over a finite field. Such points are actively used in the Pedersen vector commitment scheme and its modifications. In particular, the new approach is relevant for Pasta curves (of $j$-invariant $0$), which are very popular in the given type of elliptic cryptography. These curves are defined over highly $2$-adic fields, hence successive generation of points via a hash function to $E$ is an expensive solution. Our method also satisfies the NUMS (Nothing Up My Sleeve) principle, but it works faster on average. More precisely, instead of finding each point separately in constant time, we suggest to sample several points at once with some probability.
    Kanav Gupta, Deepak Kumaraswamy, Nishanth Chandran, Divya Gupta
    ePrint Report ePrint Report
    Secure machine learning (ML) inference can provide meaningful privacy guarantees to both the client (holding sensitive input) and the server (holding sensitive weights of the ML model) while realizing inference-as-a-service. Although many specialized protocols exist for this task, including those in the preprocessing model (where a majority of the overheads are moved to an input independent offline phase), they all still suffer from large online complexity. Specifically, the protocol phase that executes once the parties know their inputs, has high communication, round complexity, and latency. Function Secret Sharing (FSS) based techniques offer an attractive solution to this in the trusted dealer model (where a dealer provides input independent correlated randomness to both parties), and 2PC protocols obtained based on these techniques have a very lightweight online phase. Unfortunately, current FSS-based 2PC works (AriaNN, PoPETS 2022; Boyle et al. Eurocrypt 2021; Boyle et al. TCC 2019) fall short of providing a complete solution to secure inference. First, they lack support for math functions (e.g., sigmoid, and reciprocal square root) and hence, are insufficient for a large class of inference algorithms (e.g. recurrent neural networks). Second, they restrict all values in the computation to be of the same bitwidth and this prevents them from benefitting from efficient float-to-fixed converters such as Tensorflow Lite that crucially use low bitwidth representations and mixed bitwidth arithmetic. In this work, we present LLAMA -- an end-to-end, FSS based, secure inference library supporting precise low bitwidth computations (required by converters) as well as provably precise math functions; thus, overcoming all the drawbacks listed above. We perform an extensive evaluation of LLAMA and show that when compared with non-FSS based libraries supporting mixed bitwidth arithmetic and math functions (SIRNN, IEEE S&P 2021), it has at least an order of magnitude lower communication, rounds, and runtimes. We integrate LLAMA with the EzPC framework (IEEE EuroS&P 2019) and demonstrate its robustness by evaluating it on large benchmarks (such as ResNet-50 on the ImageNet dataset) as well as on benchmarks considered in AriaNN -- here too LLAMA outperforms prior work.
    Chunfu Jia, Shaoqiang Wu, Ding Wang
    ePrint Report ePrint Report
    As the most dominant authentication mechanism, password-based authentication suffers catastrophic offline password guessing attacks once the authentication server is compromised and the password database is leaked. Password hardening (PH) service, an external/third-party crypto service, has been recently proposed to strengthen password storage and reduce the damage of authentication server compromise. However, all existing schemes are unreliable because they overlook the important restorable property: PH service opt-out. In existing PH schemes, once the authentication server has subscribed to a PH service, it must adopt this service forever, even if it wants to stop the external/third-party PH service and restore its original password storage (or subscribe to another PH service).

    To fill the gap, we propose a new PH service called PW-Hero that equips its PH service with an option to terminate its use (i.e., opt-out). In PW-Hero, password authentication is strengthened against offline attacks by adding external secret spices to password records. With the opt-out property, authentication servers can proactively request to end the PH service after successful authentications. Then password records can be securely migrated to their traditional salted hash state, ready for subscription to other PH services. Besides, PW-Hero achieves all existing desirable properties, such as comprehensive verifiability, rate limits against online attacks, and user privacy. We define PW-Hero as a suite of protocols that meet desirable properties and build a simple, secure, and efficient instance. Moreover, we develop a prototype implementation and evaluate its performance, which shows the practicality of our PW-Hero service.
    Ilan Komargodski, Shin’ichiro Matsuo, Elaine Shi, Ke Wu
    ePrint Report ePrint Report
    It is well-known that in the presence of majority coalitions, strongly fair coin toss is impossible. A line of recent works have shown that by relaxing the fairness notion to game theoretic, we can overcome this classical lower bound. In particular, Chung et al. (CRYPTO'21) showed how to achieve approximately (game-theoretically) fair leader election in the presence of majority coalitions, with round complexity as small as $O(\log \log n)$ rounds.

    In this paper, we revisit the round complexity of game-theoretically fair leader election. We construct $O(\log^* n)$ rounds leader election protocols that achieve $(1-o(1))$-approximate fairness in the presence of $(1-o(1)) n$-sized coalitions. Our protocols achieve the same round-fairness trade-offs as Chung et al.'s and have the advantage of being conceptually simpler. Finally, we also obtain game-theoretically fair protocols for committee election which might be of independent interest.