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:
02 November 2022
Florida Atlantic University
The Department of Mathematical Sciences at Florida Atlantic University invites applications for a tenure-track position at the assistant professor level in the area of cryptology, starting in August 2023. We will consider applicants knowledgeable in the general area of cryptology. Preference will be given to candidates with several broad areas of interest including, but not limited to, mathematical foundations of public-key cryptography, post-quantum cryptography (e.g., based on error-correcting codes, lattice problems, or polynomial systems of equations), and algorithmic number theory. In general, we will give higher priority to the overall originality and promise of the candidate’s work rather than to the sub-area specialization.
Responsibilities for this position will be research, teaching, and professional service.
The successful candidate is expected to apply for and secure external research funding, and actively participate in interdisciplinary programs.
The Department of Mathematical Sciences is a collegial and research-active department demonstrating excellence in teaching, research, and service. We are home to 27 tenure-track or tenured faculty members, 15 faculty members in non-tenure-track positions, and more than 40 graduate teaching/research assistants from diverse backgrounds. Our department has an established national and international reputation for research innovation through our Center for Cryptology and Information Security. FAU is also recognized as a National Center of Academic Excellence in Information Assurance/Cyber Defense Research (CAE-R) for academic years 2019-2024. More information about the department can be found at: http://www.math.fau.edu/
Diversity and Inclusion are core values of the Department of Mathematical Sciences. We believe that the educational environment is enhanced when diverse groups of people with diverse ideas come together to learn. Applicants whose work incorporates a global perspective and a demonstrated commitment to diversity of thought in higher education are particularly encouraged to apply.
Review of applications will begin January 15, 2023 and will continue until the position is filled.
Closing date for applications:
Contact: Informal inquiries can be addressed to: Dr. Edoardo Persichetti, Chair of the Search Committee, (epersichetti@fau.edu). Apply at https://fau.wd1.myworkdayjobs.com/FAU/job/Boca-Raton/Assistant-Professor--Cryptology_REQ14641
More information: https://fau.wd1.myworkdayjobs.com/FAU/job/Boca-Raton/Assistant-Professor--Cryptology_REQ14641
NYU Shanghai, Engineering and Computer Science; Shanghai, China
NYU Shanghai is currently inviting applications for Tenured or Tenure-Track positions in Computer Science. The search is not restricted to any rank and outstanding candidates at all levels are encouraged to apply. We seek candidates who have completed a Ph.D. in Computer Science, or a closely related discipline. We seek candidates in all sub-fields of Computer Science, with particular interest in Systems, Computer Science Theory, Quantum Computing, Artificial Intelligence and Deep Learning.
Review of applications will begin on January 1, 2023 and will continue until the position is filled. To find more information about NYU Shanghai and apply, please follow this link https://apply.interfolio.com/116511. If you have any questions, please email the NYU Shanghai NY Office of Faculty Recruitment shanghai.faculty.recruitment@nyu.edu.
Terms of employment at NYU Shanghai are comparable to NYU New York and other U.S. institutions with respect to research start-up funds and compensation, and they include housing subsidies and educational subsidies for children. Faculty may in certain cases have the opportunity to spend time at NYU New York and other sites of the NYU Global Network, engaging in both research and teaching.
Closing date for applications:
Contact: NYU Shanghai NY Office of Faculty Recruitment: shanghai.faculty.recruitment@nyu.edu
More information: https://apply.interfolio.com/116511
Vernam Lab, Worcester Polytechnic Institute; Worcester, USA.
Multiple fully funded Ph.D. positions are available at the Vernam Lab (http://vernam.wpi.edu). Thanks to the rolling admission, prospective Ph.D. students can join us in January 2023 at the earliest. The hiring process runs until suitable candidates have been selected. The students are expected to work on a wide variety of topics that are mainly related to hardware security, including:
(1) side-channel analysis and fault analysis,
(2) application of artificial intelligence in hardware security,
(3) security of deep learning hardware accelerators,
(4) electronic design automation and verification,
(5) cryptographic implementation in hardware as well as software, and
(6) physical security of cryptographic hardware.
Requirements
What does Vernam Lab offer? A competitive salary and an international cutting-edge research program in an attractive working environment.
WPI is a highly-ranked research university in the Boston area and has been recently recognized by the 2020 HEED Award for its outstanding commitment to diversity and inclusion. In accordance with this mission and to broaden participation in STEM, we encourage all students, especially minority students, to apply. Interested students should contact us by sending an email with a CV to vernam.labs@gmail.com.
Requirements
-
• A degree in ECE or CS
• Strong background in mathematics and computer engineering
• Prior experience in one or more of the following is a plus:
-
o Cryptography
o Machine learning
o Programming languages: Python (open to work with new libraries), VHDL/Verilog
o FPGA prototyping, lab equipment (hands-on experience)
What does Vernam Lab offer? A competitive salary and an international cutting-edge research program in an attractive working environment.
WPI is a highly-ranked research university in the Boston area and has been recently recognized by the 2020 HEED Award for its outstanding commitment to diversity and inclusion. In accordance with this mission and to broaden participation in STEM, we encourage all students, especially minority students, to apply. Interested students should contact us by sending an email with a CV to vernam.labs@gmail.com.
Closing date for applications:
Contact: vernam.labs@gmail.com
01 November 2022
Gora Adj, Luis Rivera-Zamarripa, Javier Verbel
In recent years, many digital signature scheme proposals have been built from the so-called MPC-in-the-head paradigm.
This has shown to be an outstanding way to design efficient signatures with security based on hard problems.
MinRank is an NP-complete problem extensively studied due to its applications to cryptanalysis since its introduction in 1999. However, only a few schemes base their security on its intractability, and their signature size is large compared with other proposals based on NP problems. This paper introduces the first MinRank-based digital signature scheme that uses the MPC-in-the-head, enabling it to achieve small signature sizes and running times. For NIST's category I parameter set, we obtain signatures of 6.5KB, which is competitive with the shortest proposals in the literature that are based on non-structured problems.
MinRank is an NP-complete problem extensively studied due to its applications to cryptanalysis since its introduction in 1999. However, only a few schemes base their security on its intractability, and their signature size is large compared with other proposals based on NP problems. This paper introduces the first MinRank-based digital signature scheme that uses the MPC-in-the-head, enabling it to achieve small signature sizes and running times. For NIST's category I parameter set, we obtain signatures of 6.5KB, which is competitive with the shortest proposals in the literature that are based on non-structured problems.
Susan Hohenberger, George Lu, Brent Waters, David J. Wu
Attribute-based encryption (ABE) generalizes public-key encryption and enables fine-grained control to encrypted data. However, ABE upends the traditional trust model of public-key encryption by requiring a single trusted authority to issue decryption keys. A compromised central authority has the ability to decrypt every ciphertext in the system.
This work introduces registered ABE, a primitive that allows users to generate secret keys on their own and then register the associated public key with a "key curator" along with their attributes. The key curator aggregates the public keys from the different users into a single compact master public key. To decrypt, users occasionally need to obtain helper decryption keys from the key curator which they combine with their own secret keys. We require that the size of the aggregated public key, the helper decryption keys, the ciphertexts, as well as the encryption/decryption times to be polylogarithmic in the number of registered users. Moreover, the key curator is entirely transparent and maintains no secrets. Registered ABE generalizes the notion of registration-based encryption (RBE) introduced by Garg et al. (TCC 2018), who focused on the simpler setting of identity-based encryption.
We construct a registered ABE scheme that supports an a priori bounded number of users and policies that can be described by a linear secret sharing scheme (e.g., monotone Boolean formulas) from assumptions on composite-order pairing groups (the same pairing-based assumptions previously used to construct vanilla ABE). Notably, our approach deviates sharply from previous techniques for constructing RBE and only makes black-box use of cryptography. All existing RBE constructions (a weaker notion than registered ABE) rely on heavy non-black-box techniques. In fact, the encryption and decryption costs of our construction are comparable to those of vanilla pairing-based ABE. Finally, as a feasibility result, we show how to construct a registered ABE scheme that supports general policies and an arbitrary number of users from indistinguishability obfuscation and somewhere statistically binding hash functions.
This work introduces registered ABE, a primitive that allows users to generate secret keys on their own and then register the associated public key with a "key curator" along with their attributes. The key curator aggregates the public keys from the different users into a single compact master public key. To decrypt, users occasionally need to obtain helper decryption keys from the key curator which they combine with their own secret keys. We require that the size of the aggregated public key, the helper decryption keys, the ciphertexts, as well as the encryption/decryption times to be polylogarithmic in the number of registered users. Moreover, the key curator is entirely transparent and maintains no secrets. Registered ABE generalizes the notion of registration-based encryption (RBE) introduced by Garg et al. (TCC 2018), who focused on the simpler setting of identity-based encryption.
We construct a registered ABE scheme that supports an a priori bounded number of users and policies that can be described by a linear secret sharing scheme (e.g., monotone Boolean formulas) from assumptions on composite-order pairing groups (the same pairing-based assumptions previously used to construct vanilla ABE). Notably, our approach deviates sharply from previous techniques for constructing RBE and only makes black-box use of cryptography. All existing RBE constructions (a weaker notion than registered ABE) rely on heavy non-black-box techniques. In fact, the encryption and decryption costs of our construction are comparable to those of vanilla pairing-based ABE. Finally, as a feasibility result, we show how to construct a registered ABE scheme that supports general policies and an arbitrary number of users from indistinguishability obfuscation and somewhere statistically binding hash functions.
Markku-Juhani O. Saarinen
Side-channel secure implementations of public-key cryptography algorithms must be able to load and store their secret keys safely. We describe WrapQ, a masking-friendly key management technique and encoding format for Kyber and Dilithium Critical Security Parameters (CSPs). WrapQ protects secret key integrity and confidentiality with a Key-Encrypting Key (KEK) and allows the keys to be stored on an untrusted medium. Importantly, its encryption and decryption processes avoid temporarily collapsing the masked asymmetric secret keys (which are plaintext payloads from the viewpoint of the wrapping primitive) into an unmasked format. We demonstrate that a masked Kyber or Dilithium private key can be loaded any number of times from a compact WrapQ format without updating the encoding in non-volatile memory. We also consider the keys-in-RAM use case (without the write-back restriction) and introduce Mask Compression, a technique that leverages fast, unmasked deterministic samplers. Mask compression saves working memory while reducing the need for true randomness and is especially useful when higher-order masking is applied in lattice cryptography. The techniques have been implemented in a side-channel secure hardware module. Kyber and Dilithium wrapping and unwrapping functions were validated with 100K traces of TVLA-type leakage assessment.
Peter Chvojka, Tibor Jager
Timed commitment schemes, introduced by Boneh and Naor (CRYPTO 2000), can be used to achieve fairness in secure computation protocols in a simple and elegant way. The only known non-malleable construction in the standard model is due to Katz, Loss, and Xu (TCC 2020). This construction requires general-purpose zero knowledge proofs with specific properties, and it suffers from an inefficient commitment protocol, which requires the committing party to solve a computationally expensive puzzle.
We propose new constructions of non-malleable non-interactive timed commitments, which combine (an extension of) the Naor-Yung paradigm used to construct IND-CCA secure encryption with a non-interactive ZK proofs for a simple algebraic language. This yields much simpler and more efficient non-malleable timed commitments in the standard model.
Furthermore, our constructions also compare favourably to known constructions of timed commitments in the random oracle model, as they achieve several further interesting properties that make the schemes very practical. This includes the possibility of using a homomorphism for the forced opening of multiple commitments in the sense of Malavolta and Thyagarajan (CRYPTO 2019), and they are the first constructions to achieve public verifiability, which seems particularly useful to apply the homomorphism in practical applications.
We propose new constructions of non-malleable non-interactive timed commitments, which combine (an extension of) the Naor-Yung paradigm used to construct IND-CCA secure encryption with a non-interactive ZK proofs for a simple algebraic language. This yields much simpler and more efficient non-malleable timed commitments in the standard model.
Furthermore, our constructions also compare favourably to known constructions of timed commitments in the random oracle model, as they achieve several further interesting properties that make the schemes very practical. This includes the possibility of using a homomorphism for the forced opening of multiple commitments in the sense of Malavolta and Thyagarajan (CRYPTO 2019), and they are the first constructions to achieve public verifiability, which seems particularly useful to apply the homomorphism in practical applications.
Yusuf Alnawakhtha, Atul Mantri, Carl A. Miller, Daochen Wang
Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-$X$ or $Z$ measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the $XY$-plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the $XY$-plane up to a Pauli-$Z$ correction.
Yaniv Kleinman, Shlomi Dolev
A new CRT-based positive (non-zero) secret-sharing scheme with perfect information-theoretic (PIT) security and multiplicative homomorphism is presented. The scheme is designed to support the evaluation of multiplications of non-zero secrets of multiplicative groups.
Our CRT-based scheme is partially homomorphic, supporting homomorphic multiplications. Nevertheless, our scheme has the potential to be regarded as fully homomorphic for practical scenarios, such as bounded-sized multi-cloud databases.
Our CRT-based scheme is partially homomorphic, supporting homomorphic multiplications. Nevertheless, our scheme has the potential to be regarded as fully homomorphic for practical scenarios, such as bounded-sized multi-cloud databases.
Eun-Young Seo, Young-Sik Kim, Joon-Woo Lee, Jong-Seon No
FALCON and Crystals-Dilithium are the digital signatures algorithms selected as NIST PQC standards at the end of the third round. FALCON has the advantage of the shortest size of the combined public key and signature but has the disadvantage of the relatively long signing time. Since FALCON algorithm is faithfully designed based on theoretical security analysis, the implementation of the algorithms is quite complex and needs considerable complexity. In order to implement the FALCON algorithm, the isochronous discrete Gaussian sampling algorithm should be used to prevent the side-channel attack, which causes a longer signature time. Also, FFT operations with floating-point numbers should be performed in FALCON, and they cause difficulty in applying the masking technique, making it vulnerable to side-channel attacks. We propose the Peregrine signature algorithm by devising two methods to make the signing algorithm of the FALCON scheme efficient. To reduce the signing time, Peregrine replaces the discrete Gaussian sampling algorithm with the sampling algorithm from the centered binomial distribution in the key generation algorithm and the signing algorithm by adjusting the encryption parameters. Also, it replaces the fast Fourier transform (FFT) operations of floating-point numbers with the number theoretic transform (NTT) operations of integers represented in residue number system (RNS), making the scheme faster and easy to be applied with a masking technique to prevent the side channel attack.
Yonatan Sompolinsky, Michael Sutton
In 2008 Satoshi wrote the first permissionless consensus protocol, known as Nakamoto Consensus (NC), and implemented in Bitcoin. A large body of research was dedicated since to modify and extend NC, in various aspects: speed, throughput, energy consumption, computation model, and more. One line of work focused on alleviating the security-speed tradeoff which NC suffers from by generalizing Satoshi's blockchain into a directed acyclic graph of blocks, a block DAG. Indeed, the block creation rate in Bitcoin must be suppressed in order to ensure that the block interval is much smaller than the worst case latency in the network. In contrast, the block DAG paradigm allows for arbitrarily high block creation rate and block sizes, as long as the capacity of nodes and of the network backbone are not exceeded. Still, these protocols, as well as other permissionless protocols, assume an a priori bound on the worst case latency, and hardcode a corresponding parameter in the protocol. Confirmation times then depend on this worst case bound, even when the network is healthy and messages propagate very fast. In this work we set out to alleviate this constraint, and create the first permissionless protocol which contains no a priori in-protocol bound over latency. DAG-KNIGHT is thus responsive to network conditions, while tolerating a corruption of up to 50% of the computational power (hashrate) in the network. To circumvent an impossibility result by Pass and Shi, we require that the client specifies locally an upper bound over the maximum adversarial recent latency in the network. DAG-KNIGHT is an evolution of the PHANTOM paradigm, which is a parameterized generalization of NC.
Jong-Seon No, Jinkyu Cho, Yongwoo Lee, Zahyun Koo, Young-Sik Kim
We present a novel code-based digital signature scheme, called enhanced pqsigRM for post-quantum cryptography (PQC).
This scheme is based on a modified Reed--Muller (RM) code, which reduces the signature size and verification time compared with existing code-based signature schemes.
In fact, it strengthens pqsigRM submitted to NIST for post-quantum cryptography standardization.
The proposed scheme has the advantage of the short signature size and fast verification and uses public codes that are more difficult to distinguish from random codes.
We use $(U,U+V)$-codes with the high-dimensional hull to overcome the disadvantages of code-based schemes.
The proposed decoder samples from coset elements with small Hamming weight for any given syndrome and efficiently finds such an element.
Using a modified RM code, the proposed signature scheme resists various known attacks on RM-code-based cryptography.
It has advantages on signature size, verification time, and proven security.
For 128 bits of classical security, the signature size of the proposed signature scheme is 512 bytes, which corresponds to 1/4.7 of that of CRYSTALS-DILITHIUM, and the number of median verification cycles is 759,248, which corresponds to the twice of that of CRYSTALS-DILITHIUM.
Oguzhan Akcin, Robert P. Streit, Benjamin Oommen, Sriram Vishwanath, Sandeep Chinchali
There are a multitude of Blockchain-based physical infrastructure systems, ranging from decentralized 5G wireless to electric vehicle charging networks. These systems operate on a crypto-currency enabled token economy, where node suppliers are rewarded with tokens for enabling, validating, managing and/or securing the system. However, today's token economies are largely designed without infrastructure systems in mind, and often operate with a fixed token supply (e.g., Bitcoin). Such fixed supply systems often encourage early adopters to hoard valuable tokens, thereby resulting in reduced incentives for new nodes when joining or maintaining the network. This paper argues that token economies for infrastructure networks should be structured differently - they should continually incentivize new suppliers to join the network to provide services and support to the ecosystem. As such, the associated token rewards should gracefully scale with the size of the decentralized system, but should be carefully balanced with consumer demand to manage inflation and be designed to ultimately reach an equilibrium. To achieve such an equilibrium, the decentralized token economy should be adaptable and controllable so that it maximizes the total utility of all users, such as achieving stable (overall non-inflationary) token economies.
Our main contribution is to model infrastructure token economies as dynamical systems - the circulating token supply, price, and consumer demand change as a function of the payment to nodes and costs to consumers for infrastructure services. Crucially, this dynamical systems view enables us to leverage tools from mathematical control theory to optimize the overall decentralized network’s performance. Moreover, our model extends easily to a Stackelberg game between the controller and the nodes, which we use for robust, strategic pricing. In short, we develop predictive, optimization-based controllers that outperform traditional algorithmic stablecoin heuristics by up to $2.4 \times$ in simulations based on real demand data from existing decentralized wireless networks.
30 October 2022
Siwei Sun, Tianyu Liu, Zhi Guan, Yifei He, Jiwu Jing, Lei Hu, Zhenfeng Zhang, Hailun Yan
We instantiate the hash-based post-quantum stateful signature schemes LMS and LMS described in RFC 8554 and NIST SP 800-208 with SM3, and report on the results of the preliminary performance test.
Marcio Barbado Junior
Quantum computing threatens classical cryptography, leading to the search for stronger alternatives. The cryptographic approach based on lattices is considered as a viable option. Schemes with that approach use Gaussian sampling, a design which brings along two concerns: efficiency and information leakage. This work addresses those concerns in the RLWE formulation, for digital signatures. Efficiency mitigation uses the central limit theorem, and the Walsh–Hadamard transform, whereas the information leakage risk is reduced via isochronous implementation. Up to \( 2^{23} \) samples are queried, and the results are compared against those of a cumulative distribution table sampler. Statistical metrics show the suitability of the presented sampler in a number of contexts.
Vasyl Ustimenko
For arbitrary finite field F_q, q > 2 we prove that known qregular bipartite algebraic graphs A(n; q) existence on 2q^n vertices have
girth 2n or 2n + 2. Similar result is formulated for more general graphs
A(n; K) defined over general commutative integrity ring K. The impact
of these results on Extremal Graph Theory and graph based Algebraic
Cryptography is discussed.
Thomas Kaeding
We show that a Beaufort cipher is simultaneously both a quagmire 1 and a quagmire 2 cipher, which includes it in the set of quagmire 4 ciphers as well, albeit as a degenerate one. The Beaufort is one of a family of ciphers that share this property.
Jianwei Liu, Harshad Patil, Akhil Sai Peddireddy, Kevin Singh, Haifeng Sun, Huachuang Sun, Weikeng Chen
In our survey of the various zk-EVM constructions, it becomes apparent that verifiable storage of the EVM state starts to be one of the dominating costs. This is not surprising because a big differentiator of EVM from UTXO is exactly the ability to carry states and, most importantly, their transitions, i.e., EVM is a **state** machine.
In other words, to build an efficient zk-EVM, one must first build an efficient verifiable state. The common approach, which has been used in production, is a Merkle forest to authenticate the memory that would be randomly accessed within zk-SNARK, and optimize the verification of such memory accesses.
In this note we describe a way to instantiate a Merkle tree with very few gates in TurboPlonk. We use customized gates in TurboPlonk to implement a SNARK-friendly hash function called Anemoi and its Jive k-to-1 compression mode of operation, both by Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems.
We demonstrate that with $14$ gates ($\approx1$ gate per round in a 12-round Amenoi hash), one can verify a 3-to-1 compression in a 3-ary Merkle tree. Before this, prior implementations often would require hundreds of gates. We anticipate this technique to benefit a large number of applications built off zk-SNARK.
Our implementation can be found in $\mathtt{noah}$, a library for modern privacy tokens: https://github.com/FindoraNetwork/noah
Arka Rai Choudhuri, Sanjam Garg, Abhishek Jain, Zhengzhong Jin, Jiaheng Zhang
We provide the first constructions of SNARGs for Batch-NP and P based solely on the sub-exponential Decisional Diffie Hellman (DDH) assumption. Our schemes achieve poly-logarithmic proof sizes.
Central to our results and of independent interest is a new construction of correlation-intractable hash functions for ``small input'' product relations verifiable in $\mathsf{TC}^0$, based on sub-exponential DDH.
Central to our results and of independent interest is a new construction of correlation-intractable hash functions for ``small input'' product relations verifiable in $\mathsf{TC}^0$, based on sub-exponential DDH.
Zachary A Kissel
In this work we make progress towards solving an open problem posed by Bilzhause et. al, to give constructions of redactable signature schemes that allow the signer to limit the possible redactions performed by a third party. A separate, but related notion, called controlled disclosure allows a redactor to limit future redactions. We look at two types of data, sets and linear data (data organized as a sequence). In the case of sets, we limit redactions using a policy modeled by a monotone circuit or any circuit depending on the size of the universe the set is drawn from. In the case of linear data, we give a linear construction from vector commitments that limits redactions using a policy modeled as a monotone circuit. Our constructions have the attractive feature that they are built using only blackbox techniques.