International Association
for Cryptologic Research

Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfortunately, SNARKs with desirable features such as a transparent (public-coin) setup are known only in the random oracle model (ROM). In applications this oracle must be heuristically instantiated and used in a non-black-box way.

In this paper we identify a natural oracle model, the low-degree random oracle model, in which there exist transparent SNARKs for all NP computations relative to this oracle. Informally, letting $\mathcal{O}$ be a low-degree encoding of a random oracle, and assuming the existence of (standard-model) collision-resistant hash functions, there exist SNARKs relative to $\mathcal{O}$ for all languages in $\mathsf{NP}^{\mathcal{O}}$. Such a SNARK can directly prove a computation about its own verifier. This capability leads to proof-carrying data (PCD) in the oracle model $\mathcal{O}$ based solely on the existence of (standard-model) collision-resistant hash functions.

To analyze this model, we introduce a more general framework, the linear code random oracle model (LCROM). We show how to obtain SNARKs in the LCROM for computations that query the oracle, given an accumulation scheme for oracle queries in the LCROM. Then we construct such an accumulation scheme for the special case of a low degree random oracle.

We revisit the notion of Witness Authenticated Key Exchange ($\mathsf{WAKE}$) where a party can be authenticated through a generic witness to an $\mathsf{NP}$ statement. We point out shortcomings of previous definitions, protocols and security proofs in Ngo et al. (Financial Cryptography 2021) for the (unilaterally-authenticated) two-party case. In order to overcome these limitations we introduce new models and protocols, including the first definition in literature of group witness-authenticated key exchange. We provide simple constructions based on (succinct) signatures of knowledge. Finally, we discuss their concrete performance for several practical applications in highly decentralized networks.

Homomorphic encryption (HE) is public key encryption that enables computation over ciphertexts without decrypting them, while it is known that HE cannot achieve IND-CCA2 security. To overcome this issue, the notion of keyed-homomorphic encryption (KH-PKE) was introduced, which has a separate homomorphic evaluation key and can achieve stronger security (Emura et al., PKC 2013).

The contributions of this paper are twofold. First, the syntax of KH-PKE supposes that homomorphic evaluation is performed for single operations, and its security notion called KH-CCA security was formulated based on this syntax. Consequently, if the homomorphic evaluation algorithm is enhanced in a way of gathering up sequential operations as a single evaluation, then it is not obvious whether or not KH-CCA security is preserved. In this paper, we show that KH-CCA security is in general not preserved under such modification, while KH-CCA security is preserved when the original scheme additionally satisfies circuit privacy.

Secondly, Catalano and Fiore (ACM CCS 2015) proposed a conversion method from linearly HE schemes into two-level HE schemes, the latter admitting addition and a single multiplication for ciphertexts. In this paper, we extend the conversion to the case of linearly KH-PKE schemes to obtain two-level KH-PKE schemes. Moreover, based on the generalized version of Catalano-Fiore conversion, we also construct a similar conversion from d-level KH-PKE schemes into 2d-level KH-PKE schemes.

We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order. Our algorithm only requires black-box use of the underlying Additively Homomorphic cryptosystem and generic secure computation schemes for comparison and equality testing.

We design several new protocols for private set intersection (PSI) with active security: one for the two party setting, and two protocols for the multi-party setting. In recent years, the state-of-the-art protocols for two party PSI have all been built from OT-extension. This has led to extremely efficient protocols that provide correct output to one party;~seemingly inherent to the approach, however, is that there is no efficient way to relay the result to the other party with a provable correctness guarantee. Furthermore, there is no natural way to extend this line of works to more parties. We consider a new instantiation of an older approach. Using the MPC-in-the-head paradigm of Ishai et al [IPS08], we construct a polynomial with roots that encode the intersection, without revealing the inputs. Our reliance on this paradigm allows us to base our protocol on passively secure Oblivious Linear Evaluation (OLE) (requiring 4 such amortized calls per input element). Unlike state-of-the-art prior work, our protocols provide correct output to all parties. We have implemented our protocols, providing the first benchmarks for PSI that provides correct output to all parties. Additionally, we present a variant of our multi-party protocol that provides output only to a central server.

We consider protocols for secure multi-party computation (MPC) under honest majority, i.e., for $N=2t+1$ players of which $t$ are corrupt, that achieve {guaranteed output delivery} (GOD), and in {constant latency}, independently from the circuit and $N$. A generic approach to this problem requires at least $3$ consecutive broadcasts in the plain model without PKI. State-of-the-art protocols with $2$ consecutive broadcasts, namely [GLS, Crypto'15] and [BJMS, Asiacrypt'20], however, suffer from a large size of threshold homomorphic ciphertexts. We aim for more efficient protocols in $2$ broadcasts, that subsequently enjoy a {Responsive execution}, i.e., at the speed of the network.

To achieve this goal, we design a new approach with short threshold fully homomorphic (FHE) ciphertexts, which in turn impacts the computational complexity. The main building block of our technique is a threshold encryption scheme which is Ad-Hoc, i.e., which only takes as parameter $N$ public keys independently generated, equipped with a threshold shrinking mechanism into threshold FHE ciphertexts.

One ingredient of independent interest is a linear secret sharing over RLWE rings with arbitrary modulus. By contrast, previous threshold FHE required the modulus to be prime and at least as large as $N+1$.

Another significant advantage of this approach is that it also allows an arbitrary number of lightweight {external input owners} to feed their inputs in the computation by simply encrypting them with the Ad-Hoc scheme, then go offline.

We finally prove the impossibility of $1$-Broadcast-then-Asynchronous MPC for $N\leq 3t-4$, showing tightness of our $2$ broadcasts.

Predictable arguments introduced by Faonio, Nielsen and Venturi (PKC17) are private-coin argument systems where the answer of the prover can be predicted in advance by the verifier. In this work, we study predictable arguments with additional privacy properties. While the authors in [PKC17] showed compilers for transforming PAs into PAs with zero-knowledge property, they left the construction of witness indistinguishable predictable arguments (WI-PA) in the plain model as an open problem. In this work, we first propose more efficient constructions of zero-knowledge predictable arguments (ZK-PA) based on trapdoor smooth projective hash functions (TSPHFs). Next, we consider the problem of WI-PA construction in the plain model and show how to transform PA into WI-PA using non-interactive witness-indistinguishable proofs. As a relaxation of predictable arguments, we additionally put forth a new notion of predictability called Commit-and-Prove Predictable Argument (CPPA), where except the first (reusable) message of the prover, all the prover’s responses can be predicted. We construct an efficient zero-knowledge CPPA in the non-programmable random oracle model for the class of all polynomial-size circuits. Finally, following the connection between predictable arguments and witness encryption, we show an application of CPPAs with privacy properties to the design of witness encryption schemes, where in addition to standard properties, we also require some level of privacy for the decryptors who own a valid witness for the statement used during the encryption process.

ISML (https://ai-security.github.io/index_e.htm) has conducted research in a range of areas including artificial intelligence, cyber security and cryptography. We are also extending our areas to emerging areas such as quantum computing and parallel computing. Post-doctoral research fellows are welcome from computer science/engineering, electric/electronics, and mathematics/statistics. Applicants with good high-impact journal publication records are encouraged to send their CVs via to Professor Seong Oun Hwang (seongoun.hwang at gmail.com). 1st round of application deadline: April 10, 2022 2nd round of application deadline: May 30, 2022 3rd round of application deadline: July 30, 2022

Closing date for applications:

Contact: Professor Seong Oun Hwang (seongoun.hwang at gmail.com).

More information: https://ai-security.github.io/index_e.htm

The Department of Computer Science and the School of Law at Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU) invite applications for
10 PhD positions (m/f/d) (salary level 13 TV-L) in Computer Science (full time) and Law (part time, 75%)
within the Research Training Group 2475 „Cybercrime and Forensic Computing“ funded by the German Research Foundation (DFG) commencing on October 1, 2022. The Research Training Group aims to systematically analyse research questions arising from the interaction between computer science and criminal law. The principal investigators of this project offer expertise in the following areas:

- Computer security, digital forensic science
- Criminal law, criminal procedure
- Criminology
- Theoretical computer science (logic, semantics, automata)
- Pattern recognition, image processing, image forensics
- Cryptography
- Hardware-software-co-design


More information about the project can be found at https://cybercrime.fau.de Applicants should have an excellent academic record, hold an MSc, LL.M. or an equivalent university degree in computer science, law or related disciplines, and have the goal to finish a PhD degree within three years.

Founded in 1743 and situated at the heart of the Nuremberg Metropolitan Region, FAU is a strong research university with an international perspective and one of the largest universities in Germany. FAU’s outstanding research and teaching is reflected in top positions in both national and international rankings, as well as the high amount of DFG funding which its researchers are able to secure. FAU aims to increase the number of women in scientific positions. Female candidates are therefore particularly encouraged to apply. In case of equal qualifications, candidates with disabilities will take precedence. Please submit your complete application documents by 18.4.2022 to cybercrime-applications@fau.de. Please mention in your application at least two research areas from the above list which you are specifically interested in. Interviews will commence between 7. and 10.6.2022 in Erlangen.

Closing date for applications:

Contact: Felix Freiling (felix.freiling@fau.de) regarding positions in computer science and Dominique Schröder (dominique.schroeder@fau.de) regarding cryptography.

More information: https://www.cybercrime.fau.de/stellen-open-positions/

Event date: 24 August to 30 August 2022

The Institute of Logic and Computation, research unit Security and Privacy, at TU Wien offers a position as a university assistant (post-doc) for 2 years for 40 hours/week with the possibility of an extension up to 6 years after a positive evaluation. Expected start: May 2022.

Tasks:

• Deep interest in scientific problems and the motivation for independent and goal-oriented research
• Independent teaching or participation in teaching and supervision of students
• Ability to develop methods, concepts, as well as their realization and evaluation and the willingness to contribute in interdisciplinary scientific projects
• Participation in organizational and administrative tasks of the research unit and the faculty

Your profile:

• Completion of an appropriate doctorate and in-depth knowledge of the subject area
• An outstanding publication record in top security and privacy conferences
• Research background in one of the following topics: formal methods for security and privacy, blockchain technologies, intersection between machine learning and security or privacy, or web security
• Experience in teaching and publication activities as well as interest and pleasure in research and working with students
• Organisational and analytical skills as well as a structured way of working
• Excellent skills in English communication and writing

We offer:

• Continuing personal and professional education and flexible working hours
• Central location of workplace with very good accessibility (U1/U4 Karlsplatz)
• A creative environment in one of the most liveable cities in the world
• (B1 scale, 56.861,70 EUR per year before tax)
• Additional benefits for employees

The application deadline is 28.04.2022. Online application link: https://jobs.tuwien.ac.at/Job/179063

Closing date for applications:

Contact: Matteo Maffei

More information: https://jobs.tuwien.ac.at/Job/179063

The group is renowned for its cyber security research, with currently more than 15 faculty members and over 30 researchers. It is looking for three post-docs to enhance the information security R&D. The applicants should be related to one of the following topics:

• Lattice-based cryptography
• Privacy-preserving machine learning
• Privacy and applied cryptography
• Blockchain/smart contract security

The basic requirements are:

• PhD in Computer Science, Information Security, Maths.
• Strongly related knowledge and backgrounds (e.g., research papers) of privacy-oriented cryptography (theory and/or practice).
• Professional in English (writing, speaking). Note Dutch is NOT required.

All positions will be available from September 2022 (starting with competitive salary - depending on qualifications and experience, including bonus, 30% tax ruling and other benefits). There will be great opportunities to engage with various ongoing projects, and international academia and industry partners. Please feel free to send CV, publication list and reference to the contact email.

Closing date for applications:

Contact: Dr. S. Fu (shihui.fu@tudelft.nl)

iTrust is a Cyber Security Research Center in SUTD and a National Satellite of Excellence in Singapore for securing critical infrastructure. iTrust hosts the world-class cyber-physical system (CPS) testbeds which are used for research, education, training, live-fire exercise, and technology validation. We are looking for postdocs / research fellows with expertise on cybersecurity and applied cryptography in general and CPS security in particular. The candidates should have track record of strong R&D capability, with publications at leading security conferences. The candidates familiar with maritime and shipboard OT systems will be considered with the priority. Candidate working in the current position less than one year will not be considered (unless due to the end of contract). Fresh PhD graduates are welcome. Only short-listed candidates will be contacted for interview. Successful candidates will be offered internationally competitive remuneration. Interested candidates please send your CV to Prof. Jianying Zhou. Email: jianying_zhou (at) sutd.edu.sg. Home: http://jianying.space/

Closing date for applications:

Contact: Prof. Jianying Zhou. Email: jianying_zhou (at) sutd.edu.sg

More information: http://jianying.space/

The Physical Analysis and Cryptographic Engineering (PACE), Temasek Laboratories (TL) @ Nanyang Technological University, Singapore is seeking motivated researchers, in the area of hardware security.

Candidates should ideally have already completed, or be close to completing a Master’s (with relevant experience) or PhD degree in mathematics, computer science, electrical engineering, or related disciplines, with track record in R&D (publications in international journals and conferences).

You will be joining a dynamic group performing research on embedded security. The research focus of the current roles are:

1. Hardware forensics with focus on vulnerability assessment in commercial and industrial devices.

2. Physical attack and countermeasures for novel cryptographic primitives

3. Micro-architectural attacks

This position is available from May 2022. TL offers competitive salary package plus other benefits.

Review of applications will start immediately until position is filled.

Interested candidates should send their detailed CVs, cover letter and references.

Closing date for applications:

Contact: Shivam Bhasin, Principal Investigator: sbhasin (at) ntu.edu.sg

The job holder's mission will be to:

• Develop effective (security, latency, silicon area/code size costs), countermeasures against side-channel and fault attacks, by working in conjunction with SW and HW designers
• Contribute to the definition of effective post-quantum public key cryptographic implementations
• Deploy security expertise and help ST product divisions shape the right security solutions for their products (ICs).
• Stay on top of security needs and state-of-the-art evolution, anticipating/identifying solutions and partners, developing or making available the security competences and IPs that will be needed by the Company in a 3-5 years time frame.

The candidate should have:

• An extensive background in mathematics and public key cryptography
• Knowledge of state-of-the-art side-channel and fault attacks and related countermeasures
• Teamwork, networking, customer-orientation & communication skills
• Motivation for bridging research outcomes and product design
• Experience in embedded SW design or HW design is a plus

Closing date for applications:

Contact: Matteo BOCCHI (matteo.bocchi@st.com), Ruggero SUSELLA (ruggero.susella@st.com)

More information: https://stcareers.talent-soft.com/job/job-security-engineer-m-f_18168.aspx

We provide a full-fledged security analysis of the Signal end-to-end messaging protocol within the UC framework. In particular:

(1) We formulate an ideal functionality that captures end-to-end secure messaging, in a setting with PKI and an untrusted server, against an adversary that has full control over the network and can adaptively and momentarily compromise parties at any time and obtain their entire internal states. In particular our analysis captures the forward and backwards secrecy properties of Signal and the conditions under which they break. (2) We model the various components of Signal (PKI and long-term keys, backbone "asymmetric ratchet", epoch-level symmetric ratchets, authenticated encryption) as individual ideal functionalities that are analysed separately and then composed using the UC and Global-State UC theorems. (3) We use the Random Oracle Model to model non-committing encryption for arbitrary-length messages, but the rest of the analysis is in the plain model based on standard primitives. In particular, we show how to realize Signal's key derivation functions in the standard model, from generic components, and under minimalistic cryptographic assumptions.

Our analysis improves on previous ones in the guarantees it provides, in its relaxed security assumptions, and in its modularity. We also uncover some weaknesses of Signal that were not previously discussed.

Our modeling differs from previous UC models of secure communication in that the protocol is modeled as a set of local algorithms, keeping the communication network completely out of scope. We also make extensive, layered use of global-state composition within the plain UC framework. These innovations may be of separate interest.

Double-block Hash-then-Sum (DbHtS) MACs is a class of MACs achieve beyond-birthday-bound (BBB) security, including SUM-ECBC, PMAC_Plus, 3kf9 and LightMAC_Plus etc. Recently, Shen et al. (Crypto 2021) proposed a security framework for two-key DbHtS MACs in the multi-user setting, stating that when the underlying blockcipher is ideal and the universal hash function is almost regular and universal, the two-key DbHtS MACs achieve 2n/3-bit security. Unfortunately, the regular and universal properties can not guarantee the BBB security of two-key DbHtS MACs. We propose three counter-examples which are proved to be 2n/3-bit secure in the multi-user setting by the framework, but can be broken with probability $1$ using only O(2^{n/2}) queries even in the single-user setting. We also point out the miscalculation in their proof leading to such a flaw.

In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not secure under concurrent composition, and/or (c) require proofs of security in the generic or algebraic group models. In this paper, we describe a simple three-round multiparty protocol for Schnorr signatures and prove its security. The protocol is fully simulatable, secure under concurrent composition, and proven secure in the standard model or random-oracle model (depending on the instantiations of the commitment and zero-knowledge primitives). The protocol realizes an ideal Schnorr signing functionality with perfect security in the ideal commitment and zero-knowledge hybrid model (and thus the only assumptions needed are for realizing these functionalities). We also show how to achieve proactive security and identifiable abort.

In our presentation, we do not assume that all parties begin with the message to be signed, the identities of the participating parties and a unique common session identifier, since this is often not the case in practice. Rather, the parties achieve consensus on these parameters as the protocol progresses.

We present a novel cryptographic primitive, blind accumulator, aimed at constructing e-voting systems. Blind accumulators collect private keys of eligible voters in a decentralized manner not getting information about the keys. Once the accumulation is complete, a voter processes the resulting accumulator deriving a public key that refers to the private key previously added by this voter. Public keys are derived deterministically and can therefore stand as fixed voter pseudonyms. The voter can prove that the derived key refers to some accumulated private key without revealing neither that key nor the voter itself. The voter uses the accumulated private key to sign a ballot. The corresponding public key is used to verify the signature. Since the public key is fixed, it is easy to achieve verifiability, to protect against multiple submissions of ballots by the same voter or, conversely, to allow multiple submissions but count only the last one. We suggest a syntax of blind accumulators and security requirements for them. We embed blind accumulators in the Pseudonymous Key Generation (PKG) protocol which details the use of accumulators in practical settings close to e-voting. We propose an implementation of the blind accumulator scheme whose main computations resemble the Diffie-Hellman protocol. We justify the security of the proposed implementation.

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works arXiv:1612.01011 and arXiv:1612.02689, we show that taking probabilistic mixtures of channels to solve fallback (arXiv:1409.3552) and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+$\sqrt{T}$ gate set we achieve an average non-Clifford gate count of 0.23log2(1/$\varepsilon$)+2.13 and T-count 0.56log2(1/$\varepsilon$)+5.3 with mixed fallback approximations for diamond norm accuracy $\varepsilon$. This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+$\sqrt{T}$). We also provide detailed numerical results for Clifford+T and Clifford+$\sqrt{T}$ gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.