International Association
for Cryptologic Research

Event date: 26 October to 28 October 2022
Submission deadline: 15 July 2022
Notification: 30 August 2022

Crypto 2022 will take place as a hybrid conference in Santa Barbara, USA on August 13-18 2022.

The registration is now open:
https://crypto.iacr.org/2022/registration.php

The deadline for early registration is July 15th.

Information on student stipends can be found on the same link.

Information on affiliated events can be found here:
https://crypto.iacr.org/2022/affiliated.php

This work proposes a new two-stage lattice two-stage sampling technique, generalizing the prior two-stage sampling method of Gentry, Peikert, and Vaikuntanathan (STOC '08). By using our new technique as a key building block, we can significantly improve security and efficiency of the current state of the arts of simulation-based functional encryption. Particularly, our functional encryption achieves $(Q,\poly)$ simulation-based semi-adaptive security that allows arbitrary pre- and post-challenge key queries, and has succinct ciphertexts with only an additive $O(Q)$ overhead.

Additionally, our two-stage sampling technique can derive new feasibilities of indistinguishability-based adaptively-secure $\IB$-$\FE$ for inner products and semi-adaptively-secure $\AB$-$\FE$ for inner products, breaking several technical limitations of the recent work by Abdalla, Catalano, Gay, and Ursu (Asiacrypt '20).

The SPHINCS+~[CCS '19] proposal is one of the alternate candidates for digital signatures in NIST's post-quantum standardization process. The scheme is a hash-based signature and is considered one of the most secure and robust proposals. The proposal includes a fast (but large) variant and a small (but costly) variant for each security level. The main problem that might hinder its adoption is its large signature size. Although SPHICS+ supports a tradeoff between signature size and the computational cost of the signature, further reducing the signature size (below the small variants) results in a prohibitively high computational cost for the signer (as well as the verification cost).

This paper presents several novel methods for further compressing the signature size while requiring negligible added computational costs for the signer and faster verification time. Moreover, our approach enables a much more efficient tradeoff curve between signature size and the computational costs of the signer. In many parameter settings, we achieve small signatures and faster running times simultaneously. For example, for $128$-bit security, the small signature variant of SPHINCS+ is $7856$ bytes long, while our variant is only $6304$ bytes long: a compression of approximately $20$\% while still reducing the signer's running time.

The main insight behind our scheme is that there are predefined specific subsets of messages for which the WOTS+ and FORS signatures (that SPHINCS+ uses) can be compressed and made faster (while maintaining the same security guarantees). Although most messages will not come from these subsets, we can search for suitable hashed values to sign. We sign a hash of the message concatenated with a counter that was chosen such that the hashed value is in the subset. The resulting signature is both smaller and faster to sign and verify.

Our schemes are simple to describe and implement. We provide an implementation and benchmark results.

Event date: 22 August to 24 August 2022
Submission deadline: 18 July 2022

Located at the heart of the future Green City of Benguerir, Mohammed VI Polytechnic University (UM6P), a higher education institution with an international standard, is established to serve Morocco and the African continent. Its vision is honed around research and innovation at the service of education and development. This unique nascent university, with its state-of-the-art campus and infrastructure, has woven a sound academic and research network, and its recruitment process is seeking high quality academics and professionals in order to boost its quality-oriented research environment in the metropolitan area of Marrakech.

The School of Computer and Communication Sciences at Mohammed VI Polytechnic University (UM6P), Benguerir, Morocco is currently looking for motivated and talented Postdoctoral researchers in the area of Pos-Quantum Cryptography. The successful candidates will primarily be working on the following topics (but not limited to):

• Quantum primitives such as PKE, KEM, KEX, and Digital Signatures
• Post quantum Zero Knowledge Proofs
• Design and implementation of hybrid solutions
• Attack on existing proposals

The ideal candidates should have a PhD degree in cryptography (or related field) from a leading university, and a proven record of publications in top cryptography/security/TCS venues.

We offer competitive salary (the net salary per month is 2000 USD), a budget for conference travel and research visit, and membership in a young and vibrant team with several international contacts (for more see: https://www.um6p.ma/en).

Submit your application via email including

• full CV,
• sample publications,
• a detailed research proposal,
• and 2-3 reference letters sent directly by the referees.

Applications will be considered until the position is filled.

Closing date for applications:

Contact: Assoc. Prof. Mustapha Hedabou (mustapha.hedabou@um6p.ma) https://career2.successfactors.eu/sfcareer/jobreqcareer?jobId=1339&company=ump

The Cryptography Group at the Hebrew University’s School of Computer Science and Engineering invites applications for post-doc positions. Potential applicants are encouraged to visit www.gilsegev.net and www.cs.huji.ac.il/~ilank for an overview of the group’s recent activity. To apply please provide us with your CV and research statement.

Closing date for applications:

Contact: crypto@cs.huji.ac.il

Two postdoc positions available at Monash Blockchain Technology Centre (MBTC), Monash University, Melbourne, Australia. The salary is $92,792 -- $120,093 per year (Australian dollars) plus 17% Superannuation. More can be found at https://www.jiangshanyu.com/doc/postdoc.html Interested candidates, please feel free to contact me directly via E-mail (jiangshan.yu@monash.edu).

Closing date for applications:

Contact: Jiangshan Yu

More information: https://www.jiangshanyu.com/doc/postdoc.html

At NISEC (https://research.tuni.fi/nisec/) we are looking for several Doctoral Researchers in the field of applied cryptography, hardware security, provable security and privacy.

The selected candidates will primarily be working on the following topics (but not limited to):

• Differential Privacy;
• Functional Encryption;
• Privacy-Preserving Analytics;
• Privacy-Preserving Machine Learning;
• Efficient operations on encrypted data;
• Processing of encrypted data in outsourced and untrusted environments;
• Side Channel Analysis (SCA);
• Machine Learning based SCA;
• Embedded systems security (e.g. ARM and RISC-V based SoCs);
TEE security and development (e.g. TrustZone, Trusted Applications, etc.).

Application deadline: 1 August 2022.

Closing date for applications:

Contact: Antonis Michalas (antonios.michalas AT tuni.fi) and Alejandro Cabrera Aldaya alejandro.cabreraaldaya AT tuni.fi

More information: https://bit.ly/3MAe26J

At NISEC (https://research.tuni.fi/nisec/) we are looking for several PostDoctoral Researchers in the field of applied cryptography, provable security and privacy.

The selected candidates will primarily be working on the following topics (but not limited to):

• Differential Privacy;
• Functional Encryption;
• Privacy-Preserving Analytics;
• Privacy-Preserving Machine Learning;
• Efficient operations on encrypted data;
• Processing of encrypted data in outsourced and untrusted environments.

Application deadline: 1 August 2022.

Closing date for applications:

Contact:

Antonis Michalas (https://www.amichalas.com)

More information: https://bit.ly/3NDPHhN

Orbis Labs presents a method for compiling (“arithmetizing”) relations, expressed as Σ11 formulas in the language of rings, into Halo 2 arithmetic circuits. This method offers the possibility of creating arithmetic circuits without laborious and error-prone manual circuit design and implementation, by instead expressing the relation to be arithmetized in a concise mathematical notation and generating the circuit based on that expression.

This paper studies Byzantine reliable broadcast (BRB) under asynchronous networks, and improves the state-of-the-art protocols from the following aspects. Near-optimal communication cost: We propose two new BRB protocols for $n$ nodes and input message $M$ that has communication cost $O(n|M|+n^2\log n)$, which is near-optimal due to the lower bound of $\Omega(n|M|+n^2)$. The first RBC protocol assumes threshold signature but is easy to understand, while the second RBC protocol is error-free but less intuitive. Improved computation: We propose a new construction that improves the computation cost of the state-of-the-art BRB by avoiding the expensive online error correction on the input message, while achieving the same communication cost. Balanced communication: We propose a technique named balanced multicast that can balance the communication cost for BRB protocols where the broadcaster needs to multicast the message $M$ while other nodes only needs to multicast coded fragments of size $O(|M|/n + \log n)$. The balanced multicast technique can be applied to many existing BRB protocols as well as all our new constructions in this paper, and can make every node incur about the same communication cost. Finally, we present a lower bound to show the near optimality of our protocol in terms of communication cost at each node.

We present a near-optimal asynchronous verifiable information dispersal (AVID) protocol. The total dispersal cost of our AVID protocol is $O(|M|+\kappa n^2)$, and the retrieval cost per client is $O(|M|+\kappa n)$. Unlike prior works, our AVID protocol only assumes the existence of collision-resistant hash functions. Also, in our AVID protocol, the dispersing client incurs a communication cost of $O(|M|+\kappa n)$ in comparison to $O(|M|+\kappa n\log n)$ of prior best. Moreover, each node in our AVID protocol incurs a storage cost of $O(|M|/n+\kappa)$ bits, in comparison to $O(|M|/n+\kappa \log n)$ bits of prior best. Finally, we present lower bound results on communication cost and show that our AVID protocol has near-optimal communication costs -- only a factor of $O(\kappa)$ gap from the lower bounds.

Due to the adoption of the horizontal business model with the globalization of semiconductor manufacturing, the overproduction of integrated circuits (ICs) and the piracy of intellectual properties (IPs) have become a significant threat to the semiconductor supply chain. Logic locking has emerged as a primary design-for-security measure to counter these threats. In logic locking, ICs become fully functional after fabrication only when unlocked with the correct key. However, Boolean satisfiability-based attacks have rendered most locking schemes ineffective. This gives rise to the numerous defenses and new locking methods to achieve SAT resiliency. This paper provides a unique perspective on the SAT attack efficiency based on conjunctive normal form (CNF) stored in the SAT solver. First, we show that the attack learns a new relation between key bits upon every distinguishing pattern. After each iteration, these additional clauses appended to the solver could significantly decrease the key search complexity. Second, we demonstrate that the SAT attack can break the locking scheme within the linear complexity of key size. The deviation away from linear search can be explained by the oracle's output and different logic gate types. This helps to answer how different distinguishing input eliminates fewer or more incorrect keys. Moreover, we show how key constraints on point functions affect the complexity of SAT attack. The proper key constraint on AntiSAT locking can effectively reduce the SAT attack complexity to constant 1. The same constraint minimizes the complexity of breaking CAS-Lock down to the linear range. Our analysis provides fresh perspectives on the capabilities of SAT attack, and we offer new directions to achieve SAT resiliency.

In the first part of the paper, we show a generic compiler that transforms any oracle algorithm that can query multiple oracles adaptively, i.e., can decide on which oracle to query at what point dependent on previous oracle responses, into a static algorithm that fixes these choices at the beginning of the execution. Compared to naive ways of achieving this, our compiler controls the blow-up in query complexity for each oracle individually, and causes a very mild blow-up only.

In the second part of the paper, we use our compiler to show the security of the very efficient hash-based split-key PRF proposed by Giacon, Heuer and Poettering (PKC 2018), in the quantum random-oracle model. Using a split-key PRF as the key-derivation function gives rise to a secure KEM combiner. Thus, our result shows that the hash-based construction of Giacon et al. can be safely used in the context of quantum attacks, for instance to combine a well-established but only classically-secure KEM with a candidate KEM that is believed to be quantum-secure.

Our security proof for the split-key PRF crucially relies on our adaptive-to-static compiler, but we expect our compiler to be useful beyond this particular application. Indeed, we discuss a couple of other, known results from the literature that would have profitted from our compiler, in that these works had to go though serious complications in oder to deal with adaptivity.

Private Set Intersection (PSI) allows a set of mutually distrustful parties, each holds a private data set, to compute the intersection of all sets, such that no information is revealed except for the intersection. The state-of-the-art PSI protocol (Garimella et al., CRYPTO'21) in the multi-party setting tolerating any number of malicious corruptions requires the communication bandwidth of $O(n\ell|\mathbb{F}|)$ bits for the central party $P_0$ due to the star architecture, where $n$ is the number of parties, $\ell$ is the size of each set and $|\mathbb{F}|$ is the size of an exponentially large field $\mathbb{F}$. When $n$ and $\ell$ are large, this forms an efficiency bottleneck (especially for networks with restricted bandwidthes). In this paper, we present a new multi-party PSI protocol in dishonest-majority malicious setting, which reduces the communication bandwidth of the central party $P_0$ from $O(n\ell|\mathbb{F}|)$ bits to $O(\ell|\mathbb{F}|)$ bits using a tree architecture. Furthermore, our PSI protocol reduces the expensive LPN encoding operations performed by $P_0$ by a factor of $n$ as well as the computational cost by $2n\ell$ hash operations in total. Additionally, while the multi-party PSI protocol (Garimella et al., CRYPTO'21) with a single output is secure, we present a simple attack against its multi-output extension, which allows an adversary to learn more information on the sets of honest parties beyond the intersection of all sets.

Fully homomorphic encryption~(FHE) has flourished since it was first constructed by Gentry~(STOC 2009). Single instruction multiple data~(SIMD) gave rise to efficient homomorphic operations on vectors in \((\mathbb{F}_{t^d})^\ell\), for prime \(t\). RLWE instantiated with cyclotomic polynomials of the form \(X^{2^N}+1\) dominate implementations of FHE due to highly efficient fast Fourier transformations. However, this choice yields very short SIMD plaintext vectors and high degree extension fields, e.g. \(\ell < 100, d > 100\) for small primes~(\(t = 3, 5, \dots\)).

In this work, we describe a method to encode more data on top of SIMD, \emph{Field Instruction Multiple Data}, applying reverse multiplication friendly embedding~(RMFE) to FHE. With RMFE, length-\(k\) \(\mathbb{F}_{t}\) vectors can be encoded into \(\mathbb{F}_{t^d}\) and multiplied once. The results have to be recoded~(decoded and then re-encoded) before further multiplications can be done. We introduce an FHE-specific technique to additionally evaluate arbitrary linear transformations on encoded vectors for free during the FHE recode operation. On top of that, we present two optimizations to unlock high degree extension fields with small \(t\) for homomorphic computation: \(r\)-fold RMFE, which allows products of up to \(2^r\) encoded vectors before recoding, and a three-stage recode process for RMFEs obtained by composing two smaller RMFEs. Experiments were performed to evaluate the effectiveness of FIMD from various RMFEs compared to standard SIMD operations. Overall, we found that FIMD generally had \(>2\times\) better (amortized) multiplication times compared to FHE for the same amount of data, while using almost \(k/2 \times\) fewer ciphertexts required.

We present two provably secure password-authenticated key exchange (PAKE) protocols based on a commutative group action. To date the most important instantiation of isogeny-based group actions is given by CSIDH. To model the properties more accurately, we extend the framework of cryptographic group actions (Alamati et al., ASIACRYPT 2020) by the ability of computing the quadratic twist of an elliptic curve. This property is always present in the CSIDH setting and turns out to be crucial in the security analysis of our PAKE protocols. Despite the resemblance, the translation of Diffie-Hellman based PAKE protocols to group actions either does not work with known techniques or is insecure ("How not to create an isogeny-based PAKE", Azarderakhsh et al., ACNS 2020). We overcome the difficulties mentioned in previous work by using a "bit-by-bit" approach, where each password bit is considered separately. Our first protocol $\mathsf{X\text{-}GA\text{-}PAKE}_\ell$ can be executed in a single round. Both parties need to send two set elements for each password bit in order to prevent offline dictionary attacks. The second protocol $\mathsf{Com\text{-}GA\text{-}PAKE}_\ell$ requires only one set element per password bit, but one party has to send a commitment on its message first. We also discuss different optimizations that can be used to reduce the computational cost. We provide comprehensive security proofs for our base protocols and deduce security for the optimized versions.

Since the advent of pairing-based cryptography, various optimization methods that increase the speed of pairing computations have been exploited, as well as new types of pairings. This paper extends the work of Kinoshita and Suzuki who proposed a new formula for the $ \beta$-Weil pairing on curves with even embedding degree by eliminating denominators and exponents during the computation of the Weil pairing. We provide novel formulas suitable for the parallel computation for the $\beta$-Weil pairing on curves with odd embedding degree which involve vertical line functions useful for sparse multiplications. For computations we used Miller's algorithm combined with storage and multifunction methods. Applying our framework to BLS-$27$, BLS-$15$ and BLS-$9$ curves at respectively the $256$ bit, the $192$ bit and the $128$ bit security level, we obtain faster $\beta$-Weil pairings than the previous state-of-the-art constructions. The correctness of all the formulas and bilinearity of pairings obtained in this work is verified by a SageMath code.

A software watermarking scheme can embed a message into a program while preserving its functionality. The embedded message can be extracted later by an extraction algorithm, and no one could remove it without significantly changing the functionality of the program. A watermarking scheme is public key if neither the marking procedure nor the extraction procedure needs a watermarking secret key. Prior constructions of watermarking schemes mainly focus on watermarking pseudorandom functions (PRFs), and the major open problem in this direction is to construct a public-key watermarkable PRF.

In this work, we solve the open problem via constructing public-key watermarkable PRFs with different trade-offs from various assumptions, ranging from standard lattice assumptions to the existence of indistinguishability obfuscation. To achieve the results, we first construct watermarking schemes in a weaker model, where the extraction algorithm is provided with a “hint” about the watermarked PRF key. Then we upgrade the constructions to standard watermarking schemes using a robust unobfuscatable PRF. We also provide the first construction of robust unobfuscatable PRF in this work, which is of independent interest.