International Association
for Cryptologic Research

We propose a general framework for non-universal SNARKs. It contains (1) knowledge-sound and non-black-box any-simulation-extractable (ASE), (2) zero-knowledge and subversion-zero knowledge SNARKs for the well-known QAP, SAP, QSP, and QSP constraint languages that all by design have \emph{relatively} simple security proofs. The knowledge-sound zero-knowledge SNARK is similar to Groth's SNARK from EUROCRYPT 2016, except having fewer trapdoors, while the ASE subversion-zero knowledge SNARK relies on few additional conditions. We prove security in a weaker, more realistic version of the algebraic group model. We characterize SAP, SSP, and QSP in terms of QAP; this allows one to use a SNARK for QAP directly for other languages. Our results allow us to construct a family of SNARKs for different languages and with different security properties following the same proof template. Some of the new SNARKs are more efficient than prior ones. In other cases, the new SNARKs cover gaps in the landscape, e.g., there was no previous ASE or Sub-ZK SNARK for SSP or QSP.

We propose a lattice-based digital signature scheme MLWRSign by modifying Dilithium, which is one of the third-Round finalists of NIST’s call for post-quantum cryptographic standards. To the best of our knowledge, our scheme MLWRSign is the first signature scheme whose security is based on the (module) learning with rounding (LWR) problem. Due to the simplicity of the LWR, the secret key size is reduced by approximately 30% in our scheme compared to Dilithium, while achieving the same level of security. Moreover, we implemented MLWRSign and observed that the running time of MLWRSign is comparable to that of Dilithium.

We describe and analyze a simple protocol for $n$ parties that implements a randomness beacon: a sequence of high entropy values, continuously emitted at regular intervals, with sub-linear communication per value. The algorithm can tolerate a $(1 - \epsilon)/2$ fraction of the $n$ players to be controlled by an adaptive adversary that may deviate arbitrarily from the protocol. The randomness mechanism relies on verifiable random functions (VRF), modeled as random functions, and effectively stretches an initial $\lambda$-bit seed to an arbitrarily long public sequence so that (i) with overwhelming probability in $k$--the security parameter--each beacon value has high min-entropy conditioned on the full history of the algorithm, and (ii) the total work and communication required per value is $O(k)$ cryptographic operations.

The protocol can be directly applied to provide a qualitative improvement in the security of several proof-of-stake blockchain algorithms, rendering them safe from ``grinding'' attacks.

Secure communication often require both encryption and digital signatures to guarantee the confidentiality of the message and the authenticity of the parties. However, post-quantum cryptographic protocols are often studied independently. In this work, we identify a powerful synergy between two finalist protocols in the NIST standardization process. In particular, we propose a technique that enables SABER and Dilithium to share the exact same polynomial multiplier. Since polynomial multiplication plays a key role in each protocol, this has a significant impact on hardware implementations that support both SABER and Dilithium. We estimate that existing Dilithium implementations can add support for SABER with only a 4% increase in LUT count. A minor trade-off of the proposed multiplier is that it can produce inexact results with some limited inputs. We thus carry out a thorough analysis of such cases, where we prove that the probability of these events occurring is near zero, and we show that this characteristic does not affect the security of the implementation. We then implement the proposed multiplier in hardware to obtain a design that offers competitive performance/area trade-offs. Our NTT implementation achieves a latency of 519 cycles while consuming 2,012 LUTs and only 331 flip-flops when implemented on an Artix-7 FPGA. We also propose a shuffling-based method to provide side-channel protection with low overhead during polynomial multiplication. Finally, we evaluate the side-channel security of the proposed design on a Sakura-X FPGA board.

A growing number of lightweight block ciphers are proposed for environments such as the Internet of Things. An important contribution to the reduced implementation cost is a block length n of 64 or 96 bits rather than 128 bits. As a consequence, encryption modes and message authentication code (MAC) algorithms require security beyond the 2^{n/2} birthday bound. This paper provides an extensive treatment of MAC algorithms that offer beyond birthday bound PRF security for both nonce-respecting and nonce-misusing adversaries. We study constructions that use two block cipher calls, one universal hash function call and an arbitrary number of XOR operations.

We start with the separate problem of generically identifying all possible secure n-to-n-bit pseudorandom functions (PRFs) based on two block cipher calls. The analysis shows that the existing constructions EDM, SoP, and EDMD are the only constructions of this kind that achieve beyond birthday bound security.

Subsequently we deliver an exhaustive treatment of MAC algorithms, where the outcome of a universal hash function evaluation on the message may be entered at any point in the computation of the PRF. We conclude that there are a total amount of nine schemes that achieve beyond birthday bound security, and a tenth construction that cannot be proven using currently known proof techniques. For these former nine MAC algorithms, three constructions achieve optimal n-bit security in the nonce-respecting setting, but are completely insecure if the nonce is reused. The remaining six constructions have 3n/4-bit security in the nonce-respecting setting, and only four out of these six constructions still achieve beyond the birthday bound security in the case of nonce misuse.

Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over $\mathbb F_p$ for a large prime $p$ have been recently proposed in the literature. This goal is often achieved by instantiating the non-linear layer via power maps $x\mapsto x^d$. In this paper, we start an analysis of new non-linear permutation functions over $\mathbb F_p^n$ that can be used as building blocks in such symmetric-key primitives. Given a local map $F:\mathbb F_p^m \rightarrow \mathbb F_p$, we limit ourselves to focus on S-Boxes over $\mathbb F_p^n$ for $n\ge m$ defined as $\mathcal S(x_0, x_1, \ldots, x_{n-1}) = y_0\| y_1\| \ldots \| y_{n-1}$ where $y_i := F(x_i, x_{i+1}, \ldots, x_{i+m-1} )$. As main results, we prove that

- given any quadratic function $F:\mathbb F_p^2 \rightarrow \mathbb F_p$, the corresponding S-Box $\mathcal S$ over $\mathbb F_p^n$ for $n\ge 3$ is never invertible;

- similarly, given any quadratic function $F:\mathbb F_p^3 \rightarrow \mathbb F_p$, the corresponding S-Box $\mathcal S$ over $\mathbb F_p^n$ for $n\ge 5$ is never invertible.

Moreover, for each $p\ge 3$, we present (1st) generalizations of the Lai-Massey construction over $\mathbb F_p^n$ defined as before via functions $F:\mathbb F_p^m \rightarrow \mathbb F_p$ for each $n=m\ge 2$ and (2nd) (non-trivial) quadratic functions $F:\mathbb F_p^3 \rightarrow \mathbb F_p$ such that $\mathcal S$ over $\mathbb F_p^n$ for $n\in \{3,4\}$ is invertible. As an open problem for future work, we conjecture that for each $m\ge 1$ there exists a finite integer $n_{max}(m)$ such that $\mathcal S$ over $\mathbb F_p^n$ defined as before via a quadratic function $F:\mathbb F_p^m \rightarrow \mathbb F_p$ is not invertible for each $n\ge n_{max}(m)$.

Finally, as a concrete application, we propose Neptune, a variant of the sponge hash function Poseidon, whose non-linear layer is designed by taking into account the results presented in this paper. We show that this variant leads to a concrete multiplication reduction with respect to Poseidon.

Ever since the appearance of quantum computers, prime factoring and discrete logarithm based cryptography has been put in question, giving birth to the so called post-quantum cryptography. The most prominent field in post-quantum cryptography is lattice-based cryptography, protocols that are proved to be as difficult to break as certain difficult lattice problems like Learning With Errors (LWE) or Ring Learning With Errors (RLWE). Furthermore, the application of cryptographic techniques to different areas, like electronic voting, has also seen to a great interest in distributed cryptography. In this work we will give two original threshold protocols based in the lattice problem RLWE: one for key generation and one for decryption. We will prove them both correct and secure under the assumption of hardness of some well-known lattice problems and we will give a rough implementation of the protocols in C to give some tentative results about their viability.

In this work we present a direct construction for verifiable decryption for the BGV encryption scheme by combining existing zero-knowledge proofs for linear relations and bounded values. This is one of the first constructions of verifiable decryption protocols for lattice-based cryptography, and we give a protocol that is simpler and at least as efficient as the state of the art when amortizing over many ciphertexts.

To prove its practicality we provide concrete parameters, resulting in proof size of less than $47 \tau$ KB for $\tau$ ciphertexts with message space $2048$ bits. Furthermore, we provide an open source implementation showing that the amortized cost of the verifiable decryption protocol is only $90$ ms per message when batching over $\tau = 2048$ ciphertexts.

The use of data combined with tailored statistical analysis have presented a unique opportunity to organizations in diverse fields to observe users' behaviors and needs, and accordingly adapt and fine-tune their services. However, in order to offer utilizable, plausible, and personalized alternatives to users, this process usually also entails a breach of their privacy. The use of statistical databases for releasing data analytics is growing exponentially, and while many cryptographic methods are utilized to protect the confidentiality of the data -- a task that has been ably carried out by many authors over the years -- only a few %rudimentary number of works focus on the problem of privatizing the actual databases. Believing that securing and privatizing databases are two equilateral problems, in this paper, we propose a hybrid approach by combining Functional Encryption with the principles of Differential Privacy. Our main goal is not only to design a scheme for processing statistical data and releasing statistics in a privacy-preserving way but also to provide a richer, more balanced, and comprehensive approach in which data analytics and cryptography go hand in hand with a shift towards increased privacy.

All known constructions of classical or quantum commitments require at least one-way functions. Are one-way functions really necessary for commitments? In this paper, we show that non-interactive quantum commitments (for classical messages) with computational hiding and statistical binding exist if pseudorandom quantum states exist. Pseudorandom quantum states are sets of quantum states that are efficiently generated but computationally indistinguishable from Haar random states [Z. Ji, Y.-K. Liu, and F. Song, CRYPTO 2018]. It is known that pseudorandom quantum states exist even if BQP=QMA (relative to a quantum oracle) [W. Kretschmer, TQC 2021], which means that pseudorandom quantum states can exist even if no quantum-secure classical cryptographic primitive exists. Our result therefore shows that quantum commitments can exist even if no quantum-secure classical cryptographic primitive exists. In particular, quantum commitments can exist even if no quantum-secure one-way function exists. We also show that one-time secure signatures with quantum public keys exist if pseudorandom quantum states exist. In the classical setting, the existence of signatures is equivalent to the existence of one-way functions. Our result, on the other hand, suggests that quantum signatures can exist even if no quantum-secure classical cryptographic primitive (including quantum-secure one-way functions) exists.

In this paper, we formulate a new framework of cryptanalysis called rotational-linear attack on ARX ciphers. We firstly build an efficient distinguisher for the cipher $ E$ consisted of the rotational attack and the linear attack together with some intermediate variables. Then a key recovery technique is introduced with which we can recover some bits of the last whitening key in the related-key scenario. To decrease data complexity of our attack, we also apply a new method, called bit flipping, in the rotational cryptanalysis for the first time and the effective partitioning technique to the key-recovery part. Applying the new framework of attack to the MAC algorithm Chaskey, we build a full-round distinguisher over it. Besides, we have recovered $21$ bits of information of the key in the related-key scenario, for keys belonging to a large weak-key class based on 6-round distinguisher. The data complexity is $2^{38.8}$ and the time complexity is $2^{46.8}$. Before our work, the rotational distinguisher can only be used to reveal key information by checking weak-key conditions. This is the first time it is applied in a last-rounds key-recovery attack. We build a 17-round rotational-linear distinguisher for ChaCha permutation as an improvement compared to single rotational cryptanalysis over it.

In this note, we prove the conjecture posed by Keller and Rosemarin at Eurocrypt 2021 on the nullity of a matrix polynomial of a block matrix with Hadamard type blocks over commutative rings of characteristic 2. Therefore, it confirms the conjectural optimal bound on the dimension of invariant subspace of the Starkad cipher using the HADES design strategy. We also give characterizations of the algebraic structure formed by Hadamard matrices over commutative rings.

Privacy-preserving machine learning on fully homomorphic encryption (FHE) is one of the most influential applications of the FHE scheme. Recently, Lee et al. [16] implemented the standard ResNet-20 model for the CIFAR-10 dataset with residue number system variant Cheon-Kim-Kim-Song (RNS-CKKS) scheme, one of the most promising FHE schemes, for the first time. However, its implementation should be improved because it requires large number of key-switching operations, which is the heaviest operation in the RNS-CKKS scheme. In order to reduce the number of key-switching operations, it should be studied to efficiently perform neural networks on the RNS-CKKS scheme utilizing full slots of RNS-CKKS ciphertext as much as possible. In particular, since the packing density is reduced to 1/4 whenever a convolution of stride two is performed, it is required to study convolution that maintains packing density of the data. On the other hand, when bootstrapping should be performed, it is desirable to use sparse slot bootstrapping that requires fewer key-switching operations instead of full slot bootstrapping. In this paper, we propose a new packing method that makes several tensors for multiple channels to be multiplexed into one tensor. Then, we propose new convolution method that outputs a multiplexed tensor for the input multiplexed tensor, which makes it possible to maintain a high packing density during the entire ResNet network with strided convolution. In addition, we propose a method that parallelly performs convolutions for multiple output channels using repeatedly packed input data, which reduces the running time of convolution. Further, we fine-tune the parameters to reach the standard 128-bit security level and to further reduce the number of the bootstrapping operations. As a result, the number of key-switching operations is reduced to 1/107 compared to Lee et al's implementation in the ResNet-20 model on the RNS-CKKS scheme. The proposed method takes about 37 minutes with only one thread for classification of one CIFAR-10 image compared to 3 hours with 64 threads of Lee et al.'s implementation. Furthermore, we even implement ResNet-32/44/56/110 models for the first time on RNS-CKKS scheme with the linear time of the number of layers, which is generally difficult to be expected in the leveled homomorphic encryption. Finally, we successfully classify the CIFAR-100 dataset on RNS-CKKS scheme for the first time using standard ResNet-32 model, and we obtain a running time of 3,942s and an accuracy of 69.4% close to the accuracy of backbone network 69.5%.

Due to the fact that classical computers cannot efficiently obtain random numbers, it is common practice to design cryptosystems in terms of real random numbers and then replace them with (cryptographically secure) pseudorandom ones for concrete implementations. However, as pointed out by [Nuida, PKC 2021], this technique may lead to compromise of security in secure multiparty computation (MPC) protocols. Although this work suggests using information-theoretically secure protocols and pseudorandom generators (PRGs) with high min-entropy to alleviate the problem, yet it is preferable to base the security on computational assumptions rather than the stronger information-theoretic ones. By observing that the contrived constructions in the aforementioned work use MPC protocols and PRGs that are closely related to each other, we notice that it may help to alleviate the problem by using protocols and PRGs that are "unrelated" to each other. In this paper, we propose a notion called "computational irrelevancy" to formalise the term "unrelated" and under this condition provide a security guarantee under computational assumptions.

End-to-end encryption provides strong privacy protections to billions of people, but it also complicates efforts to moderate content that can seriously harm people. To address this concern, Tyagi et al. [CRYPTO 2019] introduced the concept of asymmetric message franking (AMF), which allows people to report abusive content to a moderator, while otherwise retaining end-to-end privacy by default and even compatibility with anonymous communication systems like Signal’s sealed sender.

In this work, we provide a new construction for asymmetric message franking called Hecate that is faster, more secure, and introduces additional functionality compared to Tyagi et al. First, our construction uses fewer invocations of standardized crypto primitives and operates in the plain model. Second, on top of AMF’s accountability and deniability requirements, we also add forward and backward secrecy. Third, we combine AMF with source tracing, another approach to content moderation that has previously been considered only in the setting of non-anonymous networks. Source tracing allows for messages to be forwarded, and a report only identifies the original source who created a message. To provide anonymity for senders and forwarders, we introduce a model of "AMF with preprocessing" whereby every client authenticates with the moderator out-of-band to receive a token that they later consume when sending a message anonymously.

Event date: 9 May to 11 May 2022
Submission deadline: 20 March 2022
Notification: 1 April 2022

Ph.D. position opening (fully homomorphic encryption and related hardware implementation) at Dr. Jiafeng Harvest Xie's Security and Cryptography (SAC) Lab (https://www.ece.villanova.edu/~jxie02/lab/) in Department of Electrical and Computer Engineering, Villanova University, Villanova, PA USA.

Villanova University ranks #49 National Universities in the USA, is located in Villanova, Pennsylvania (west suburban of Philadelphia). Famous alumni include the current First Lady of the USA!

Requirements: Preferred to be in majors of EE/CE/CS, Applied Mathematics/Cryptography related majors are also warmly welcome!

Proficiency in English both speaking and writing abilities.

Skillful in programming Languages such as VHDL/Verilog, CC++, Python, and so on (FPGA-based experience is also desirable). Great enthusiasm for doing research-oriented tasks. Excellent teamwork member.

Degree: both BS and MS graduates or similar are warmly welcomed to apply.

Deadline: better to start in Summer/Fall 2022. It is always better to apply as early as possible. The position is open until it is filled.

Our lab atmosphere is peaceful and harmonious. Advisor and senior Ph.D. student will guide you to get started and work together on forthcoming challenges. You will not be fighting alone (emphasize this important thing three times!!!).

Email: jiafeng.xie@villanova.edu

This research focuses on the hardware-accelerated implementation of the combination of post-quantum cryptography and AI security (Fully Homomorphic Encryption). This direction is very new and looks promising for the next 5-n years, so a lot of research will be happening. At the same time, more opportunities are coming up, i.e., it is easier to find your development after exploring the combined research of post-quantum cryptography and AI. If you are interested, please email Dr. Xie.

Lastly, if you feel interested, please email: jiafeng.xie@villanova.edu and discuss your ideas.

Closing date for applications:

Contact: Dr. Jiafeng Harvest Xie

More information: https://www.ece.villanova.edu/~jxie02/lab/

The Computer Science and Engineering Department of the University of California, Santa Cruz invites applications for PhD students and Post-doctoral fellows in the topics of (applied) cryptography, security and privacy, secure databases and systems. Applicants should have a background/interest in cryptography, searchable encryption, databases and systems, oblivious RAM and oblivious computation, secure multi-party computation, hardware enclaves, computer & cloud security.

PhD applicants should have a bachelor/master degree in computer science, electrical & computer engineering, information security, mathematics, or any other relevant area. Excellent analytical and mathematical skills are necessary, as well as a strong background in coding and software engineering. If you are interested in research on either of the above areas you are encouraged to email me directly about your intent to apply---send me your CV and a short description of your research experience and interests, and a link to your personal website (if any). Please also submit your application here: https://grad.soe.ucsc.edu/admissions (Computer Science & Engineering→ Apply to PhD) and mention my name in your application. Note that the application fee can be waived under some conditions---please send me an email if you have any questions.

Post-doctoral applicants please email me your CV and your research statement (if available).

Closing Date for Application: January 10, 2022

Closing date for applications:

Contact: Assistant Prof. Ioannis Demertzis, idemertz (at) ucsc.edu

More information: http://idemertzis.com/UCSC_PHD_Postdoc_Openings.pdf