IACR News
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:
23 June 2022
David Heath, Yibin Yang, David Devecsery, Vladimir Kolesnikov
ePrint Report
We build a complete and efficient ZK toolchain that handles proof statements encoded as arbitrary ANSI C programs.
Zero-Knowledge (ZK) proofs are foundational in cryptography. Recent ZK research has focused intensely on non-interactive proofs of small statements, useful in blockchain scenarios. We instead target large statements that are useful, e.g., in proving properties of programs.
Recent work (Heath and Kolesnikov, CCS 2020 [HK20a]) designed a proof-of-concept ZK machine (ZKM). Their machine executes arbitrary programs over a minimal instruction set, authenticating in ZK the program execution. In this work, we significantly extend this research thrust, both in terms of efficiency and generality. Our contributions include: • A rich and performance-oriented architecture for representing arbitrary ZK proofs as programs. • A complete compiler toolchain providing full support for ANSI C95 programs. We ran off-the-shelf buggy versions of sed and gzip, proving in ZK that each program has a bug. To our knowledge, this is the first ZK system capable of executing standard Linux programs. • Improved ZK RAM. [HK20a] introduced an efficient ZK-specific RAM BubbleRAM that consumes $O(\log^2 n)$ communication per access. We extend BubbleRAM with multi-level caching, decreasing communication to $O(\log n)$ per access. This introduces the possibility of a cache miss, which we handle cheaply. Our experiments show that cache misses are rare; in isolation, i.e., ignoring other processor costs, BubbleCache improves communication over BubbleRAM by more than $8\times$. Using BubbleCache improves our processor’s total communication (including costs of cache misses) by $\approx 25-30$%. • Numerous low-level optimizations, resulting in a CPU that is both more expressive and $\approx 5.5\times$ faster than [HK20a]’s. • Attention to user experience. Our engineer-facing ZK instrumentation and extensions are minimal and easy to use.
Put together, our system is efficient and general, and can run many standard Linux programs. The resultant machine runs at up to 11KHz on a 1Gbps LAN and supports MBs of RAM.
Zero-Knowledge (ZK) proofs are foundational in cryptography. Recent ZK research has focused intensely on non-interactive proofs of small statements, useful in blockchain scenarios. We instead target large statements that are useful, e.g., in proving properties of programs.
Recent work (Heath and Kolesnikov, CCS 2020 [HK20a]) designed a proof-of-concept ZK machine (ZKM). Their machine executes arbitrary programs over a minimal instruction set, authenticating in ZK the program execution. In this work, we significantly extend this research thrust, both in terms of efficiency and generality. Our contributions include: • A rich and performance-oriented architecture for representing arbitrary ZK proofs as programs. • A complete compiler toolchain providing full support for ANSI C95 programs. We ran off-the-shelf buggy versions of sed and gzip, proving in ZK that each program has a bug. To our knowledge, this is the first ZK system capable of executing standard Linux programs. • Improved ZK RAM. [HK20a] introduced an efficient ZK-specific RAM BubbleRAM that consumes $O(\log^2 n)$ communication per access. We extend BubbleRAM with multi-level caching, decreasing communication to $O(\log n)$ per access. This introduces the possibility of a cache miss, which we handle cheaply. Our experiments show that cache misses are rare; in isolation, i.e., ignoring other processor costs, BubbleCache improves communication over BubbleRAM by more than $8\times$. Using BubbleCache improves our processor’s total communication (including costs of cache misses) by $\approx 25-30$%. • Numerous low-level optimizations, resulting in a CPU that is both more expressive and $\approx 5.5\times$ faster than [HK20a]’s. • Attention to user experience. Our engineer-facing ZK instrumentation and extensions are minimal and easy to use.
Put together, our system is efficient and general, and can run many standard Linux programs. The resultant machine runs at up to 11KHz on a 1Gbps LAN and supports MBs of RAM.
David Heath, Vladimir Kolesnikov
ePrint Report
Zero-Knowledge (ZK) proofs (ZKP) are foundational in cryptography. Most recent ZK research focuses on non-interactive proofs (NIZK) of small statements, useful in blockchain scenarios. Another line, and our focus, instead targets proofs of large statements that are useful, e.g., in proving properties of programs in ZK.
We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set and proves in ZK the correctness of the execution. Such an approach is well-suited for constructing ZK proofs of large statements as it efficiently supports complex programming constructs, such as loops and RAM access.
We propose several novel ZK improvements that make our approach concretely efficient: (1) an efficient arithmetic representation with conversions to/from Boolean, (2) an efficient read-only memory that uses $2 \log n$ OTs per access, and (3) an efficient read-write memory, BubbleRAM, which uses $1/2 \log^2 n$ OTs per access. BubbleRAM beats linear scan for RAM of size > 3 elements! Prior ZK systems used generic ORAM costing orders of magnitude more.
We cast our system as a garbling scheme that can be plugged into the ZK protocol of [Jawurek et al, CCS’13].
Put together, our system is concretely efficient: for a processor instantiated with 512KB of main memory, each processor cycle costs 24KB of communication. We implemented our approach in C++. On a 1Gbps LAN, our implementation realizes a 2.1KHz processor.
We specify a zero-knowledge processor that executes arbitrary programs written in a simple instruction set and proves in ZK the correctness of the execution. Such an approach is well-suited for constructing ZK proofs of large statements as it efficiently supports complex programming constructs, such as loops and RAM access.
We propose several novel ZK improvements that make our approach concretely efficient: (1) an efficient arithmetic representation with conversions to/from Boolean, (2) an efficient read-only memory that uses $2 \log n$ OTs per access, and (3) an efficient read-write memory, BubbleRAM, which uses $1/2 \log^2 n$ OTs per access. BubbleRAM beats linear scan for RAM of size > 3 elements! Prior ZK systems used generic ORAM costing orders of magnitude more.
We cast our system as a garbling scheme that can be plugged into the ZK protocol of [Jawurek et al, CCS’13].
Put together, our system is concretely efficient: for a processor instantiated with 512KB of main memory, each processor cycle costs 24KB of communication. We implemented our approach in C++. On a 1Gbps LAN, our implementation realizes a 2.1KHz processor.
Laura Luzzi, Cong Ling, Matthieu R. Bloch
ePrint Report
We propose a lattice-based scheme for secret key generation from Gaussian sources in the presence of an eavesdropper, and show that it achieves the strong secret key capacity in the case of degraded source models, as well as the optimal secret key / public communication rate trade-off. The key ingredients of our scheme are a lattice extractor to extract the channel intrinsic randomness, based on the notion of flatness factor, together with a randomized lattice quantization technique to quantize the continuous source. Compared to previous works, we introduce two new notions of flatness factor based on $L^1$ distance and KL divergence, respectively, which are of independent interest. We prove the existence of secrecy-good lattices under $L^1$ distance and KL divergence, whose $L^1$ and KL flatness factors vanish for volume-to-noise ratios up to $2\pi e$. This improves upon the volume-to-noise ratio threshold $2\pi$ of the $L^{\infty}$ flatness factor.
Ruize Wang, Kalle Ngo, Elena Dubrova
ePrint Report
In the ongoing last round of NIST’s post-quantum cryptography standardization competition, side-channel analysis of finalists is a main focus of attention. While their resistance to timing, power and near field electromagnetic (EM) side-channels has been thoroughly investigated, amplitude-modulated EM emanations has not been considered so far. The attacks based on amplitude-modulated EM emanations are more stealthy because they exploit side-channels intertwined into the signal transmitted by an on-chip antenna. Thus, they can be mounted on a distance from the device under attack. In this paper, we present the first results of an amplitude-modulated EM side-channel analysis of one of the NIST PQ finalists, Saber key encapsulation mechanism (KEM), implemented on the nRF52832 (ARM Cortex-M4) system-on-chip supporting Bluetooth 5. By capturing amplitude-modulated EM emanations during decapsulation, we can recover each bit of the session key with 0.91 probability on average.
Danilo Francati, Daniele Friolo, Giulio Malavolta, Daniele Venturi
ePrint Report
We put forward two natural generalizations of predicate encryption (PE) dubbed multi-key and multi-input PE. More in details, our contributions are threefold.
- Definitions. We formalize security of multi-key PE and multi-input PE following the standard indistinguishability paradigm, and modeling security both against malicious senders (i.e., corruption of encryption keys) and malicious receivers (i.e., collusions).
- Constructions. We construct multi-key and multi-input PE supporting the conjunction of poly-many arbitrary single-input predicates, assuming the hardness of the standard learning with errors (LWE) problem.
- Applications. We show that multi-key and multi-input PE for expressive enough predicates suffices for interesting cryptographic applications, including matchmaking encryption (ME) and non-interactive multi-party computation (NI-MPC).
As a corollary, plugging in our concrete constructions of multi-key and multi-input PE, we obtain the first construction of ME for arbitrary policies, as well as NI-MPC with partial re-usability for all-or-nothing functions and a constant number of parties, under the standard LWE assumption. Prior to our work, all of these applications required much heavier tools such as indistinguishability obfuscation or compact functional encryption.
- Definitions. We formalize security of multi-key PE and multi-input PE following the standard indistinguishability paradigm, and modeling security both against malicious senders (i.e., corruption of encryption keys) and malicious receivers (i.e., collusions).
- Constructions. We construct multi-key and multi-input PE supporting the conjunction of poly-many arbitrary single-input predicates, assuming the hardness of the standard learning with errors (LWE) problem.
- Applications. We show that multi-key and multi-input PE for expressive enough predicates suffices for interesting cryptographic applications, including matchmaking encryption (ME) and non-interactive multi-party computation (NI-MPC).
As a corollary, plugging in our concrete constructions of multi-key and multi-input PE, we obtain the first construction of ME for arbitrary policies, as well as NI-MPC with partial re-usability for all-or-nothing functions and a constant number of parties, under the standard LWE assumption. Prior to our work, all of these applications required much heavier tools such as indistinguishability obfuscation or compact functional encryption.
Ittai Abraham, Danny Dolev, Alon Kagan, Gilad Stern
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
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
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.
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
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
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
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.
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 date: 10 October to 14 October 2022
Submission deadline: 19 August 2022
Notification: 9 September 2022
Submission deadline: 19 August 2022
Notification: 9 September 2022
Pandit Deendayal Energy University, Gandhinagar, Guarat, India
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.
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: https://www.pdpu.ac.in/jobs.html
Graz University of Technology
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.
Responsibilities:
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: https://survey.tugraz.at/index.php/716487?lang=en
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.
Responsibilities:
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:
Please submit your application online: https://survey.tugraz.at/index.php/716487?lang=en
Closing date for applications:
Contact: If you have any specific questions about the application please contact Sujoy Sinha Roy directly: sujoy.sinharoy@iaik.tugraz.at
More information: https://survey.tugraz.at/index.php/716487?lang=en
University of Houston Downtown
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:
Contact: jobs@uhd.edu
More information: https://uhs.taleo.net/careersection/ex3_uhdf/jobdetail.ftl?job=FAC002415&tz=GMT-05%3A00&tzname=America%2FChicago
21 June 2022
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.
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
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.
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
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.
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
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.
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
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.