International Association
for Cryptologic Research

The classic work of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2012) and follow-ups provided constructions of bounded collusion Functional Encryption (FE) for circuits from mild assumptions. In this work, we improve the state of affairs for bounded collusion FE in several ways:

1. $New$ $Security$ $Notion$. We introduce the notion of $dynamic$ bounded collusion FE, where the declaration of collusion bound is delayed to the time of encryption. This enables the encryptor to dynamically choose the collusion bound for different ciphertexts depending on their individual level of sensitivity. Hence, the ciphertext size grows linearly with its own collusion bound and the public key size is independent of collusion bound. In contrast, all prior constructions have public key and ciphertext size that grow at least linearly with a fixed bound $Q$.

2. $CPFE$ $for$ $circuits$ $with$ $Dynamic$ $Bounded$ $Collusion$. We provide the first CPFE schemes for circuits enjoying dynamic bounded collusion security. By assuming identity based encryption (IBE), we construct CPFE for circuits of $unbounded$ size satisfying $non-adaptive$ simulation based security. By strengthening the underlying assumption to IBE with receiver selective opening security, we obtain CPFE for circuits of $bounded$ size, output length and depth enjoying $adaptive$ simulation based security. Moreover, we show that IBE is a necessary assumption for these primitives.

Moreover, by relying on the Learning With Errors (LWE) assumption, we obtain the first $succinct$ CPFE for circuits, i.e. supporting circuits with unbounded size, but fixed output length and depth. This scheme achieves $adaptive$ simulation based security.

3. $KPFE$ $for$ $circuits$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE for circuits of unbounded size, but bounded depth and output length satisfying dynamic bounded collusion security. Our construction relies on LWE and achieves $adaptive$ simulation based security. This improves the security of succinct KPFE by Goldwasser et al. [GKPVZ13b].

4. $KP$ $and$ $CP$ $FE$ $for$ $TM/NL$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE and CPFE constructions of bounded collusion functional encryption for Turing machines in the public key setting from LWE. Our constructions achieve non-adaptive simulation based security. Both the input and the machine in our construction can be of $unbounded$ polynomial length but the ciphertext size grows with the upper bound on the running time of the Turing machine on the given input. Given RAM access to the ciphertext, the scheme enjoys input specific decryption time.

We provide a variant of the above scheme that satisfies $adaptive$ security, but at the cost of supporting a smaller class of computation, namely Nondeterministic Logarithmic-space (NL). Since NL contains Nondeterministic Finite Automata (NFA), this result subsumes $all$ prior work of bounded collusion FE for uniform models from standard assumptions [AMY19,AS17].

Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ function keys. A major drawback of such \emph{statically} bounded collusion systems is that the collusion bound $q$ must be declared at setup time and is fixed for the entire lifetime of the system.

We initiate the study of \emph{dynamically} bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions). Briefly, the virtues of a dynamically bounded scheme can be summarized as:

(i) [Fine-grained individualized selection.] It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience.

(ii) [Evolving encryption strategies.] Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc.

(iii) [Ease and simplicity of updatability.] None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key $\mathsf{sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$.

We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption.

This is team SmartPools’ submission for the first Ergo Hackathon. It suggests that Ergo lacks the decentralization, and focus on regular people that it was designed for, and presents a potential solution for these problems in laying the framework for crowdfunded smart contract pools compatible with non-outsourceabilty. It should allow for pool formation with a greater level of decentralization than previously possible by including metrics for diminishing returns on over-contributing hash power to pools with data gathered from Ergo Oracles. This work is informal and preliminary. Further research is required to formalize this work and attempt to provide functional proof for its arguments; readers are highly encouraged to read the included references, and their references, for greater clarity.

Digital signature schemes form the basis of trust in Internet communication. Shor (FOCS 1994) proposed quantum algorithms that can be used by a quantum computer to break the security of today’s widely used digital signature schemes, and this has fuelled intensive research on the design and implementation of post-quantum digital signatures. Hash-based digital signatures base their security on one-way functions that in practice are instantiated by hash functions. Hash-based signatures are widely studied and are part of NIST's post-quantum standardization effort.

In this paper we present a multi-target attack that we call Intermediate Secret-Guessing attack on two hash-based signatures: XMSS^MT (Draft SP 800-208 that was considered by NIST for standardization), and K2SN-MSS (AsiaCCS 2019). The attack allows an adversary to forge a signature on an arbitrary message. We describe the intuition behind the attack and give details of its application on the attacked schemes together with corresponding theoretical analysis. The attack implies that the effective security levels of XMSS (a special case of XMSS^MT), XMSS^MT, and K2SN-MSS are 10, 39 and 12 bits lower than their designed security levels given access to $2^{20}$, $2^{60}$, and $2^{20}$ signatures, respectively.

We implement the attack for each scheme, and give our results for reduced security parameters that validate our theoretical analysis. We also show that the attack can be avoided by modifying the application of a pseudorandom function for key generation. Our work shows the subtleties of replacing randomness with pseudo-randomness in the key generation of hash-based signatures, and the need for careful analysis of such designs.

We show in this note that bounded KEM IND-CCA security (IND-qCCA) is easily obtained from any passively secure PKE in the (Q)ROM. That is, simply adding a confirmation hash or computing the key as the hash of the plaintext and ciphertext holds an IND-qCCA KEM. In particular, there is no need for derandomization or re-encryption as in the Fujisaki-Okamoto transform. Such KEMs could be used in the recently proposed KEMTLS protocol [ACM CCS 2020] that requires IND-1CCA ephemeral key-exchange mechanisms. We also highlight and briefly discuss several use cases of IND-1CCA KEMs in TLS and ratcheting primitives.

Starting with the work of Rivest et al. in 1996, timed assumptions have found many applications in cryptography, building e.g. the foundation of the blockchain technology. They also have been used in the context of classical MPC, e.g. to enable fairness. We follow this line of research to obtain composable generic MPC in the plain model. This approach comes with a major advantage regarding environmental friendliness, a property coined by Canetti et al. (FOCS 2013). Informally, this means that our constructions do not “hurt” game-based security properties of protocols that hold against polynomial-time adversaries when executed alone. As an additional property, they can be plugged into any UC-secure protocol without loss of security. Towards proving the security of our constructions, we introduce a variant of the UC security notion that captures timed cryptographic assumptions. Combining standard timed commitments and standard polynomial-time hardness assumptions, we construct a composable commitment scheme in the plain model. As this construction is constant-round and black-box, we obtain the first fully environmentally friendly composable constant-round black-box generic MPC protocol in the plain model from standard (timed) assumptions.

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary's power in other information theoretic proof-systems and show how to use this assumption to bypass impossibility results.

We first consider the question of constructing succinct PCPs. These are PCPs whose length is polynomial only in the length of the original NP witness (in contrast to standard PCPs whose length is proportional to the non-deterministic verification time). Unfortunately, succinct PCPs are known to be impossible to construct under standard complexity assumptions. Assuming the sub-exponential hardness of the learning with errors (LWE) problem, we construct succinct probabilistically checkable arguments or PCAs (Zimand 2001, Kalai and Raz 2009), which are PCPs in which soundness is guaranteed against efficiently generated false proofs. Our PCA construction is for every NP relation that can be verified by a small-depth circuit (e.g., SAT, clique, TSP, etc.) and in contrast to prior work is publicly verifiable and has constant query complexity. Curiously, we also show, as a proof-of-concept, that such publicly-verifiable PCAs can be used to derive hardness of approximation results.

Second, we consider the notion of Instance Compression (Harnik and Naor, 2006). An instance compression scheme lets one compress, for example, a CNF formula $\varphi$ on $m$ variables and $n \gg m$ clauses to a new formula $\varphi'$ with only $poly(m)$ clauses, so that $\varphi$ is satisfiable if and only if $\varphi'$ is satisfiable. Instance compression has been shown to be closely related to succinct PCPs and is similarly highly unlikely to exist. We introduce a computational analog of instance compression in which we require that if $\varphi$ is unsatisfiable then $\varphi'$ is effectively unsatisfiable, in the sense that it is computationally infeasible to find a satisfying assignment for $\varphi'$ (although such an assignment may exist). Assuming the same sub-exponential LWE assumption, we construct such computational instance compression schemes for every bounded-depth NP relation. As an application, this lets one compress $k$ formulas $\phi_1,\dots,\phi_k$ into a single short formula $\phi$ that is effectively satisfiable if and only if at least one of the original formulas was satisfiable.

Event date: 16 December to 18 December 2021
Submission deadline: 26 July 2021
Notification: 6 September 2021

Event date: 2 December to 4 December 2021
Submission deadline: 31 August 2021
Notification: 31 October 2021

Event date: 9 November to 13 November 2021
Submission deadline: 7 July 2021
Notification: 30 August 2021

King Khaled University announces an opportunity to apply for an Assistant Professor and above job in Abha, Kingdom of Saudi Arabia at College of Computer Science. The College of Computer Science has 3 Programs in Information Security namely MSc in Information Security, High Diploma in Cyber Security and Information Security tracks in three BSc programs (Computer Science, Information Systems and Computer Engineering).

Closing date for applications:

Contact: Dr. Sarah Abu Ghazalah sabugazalah@kku.edu.sa

More information: https://cs.kku.edu.sa/en

We are currently seeking to recruit a Post-Doctoral Researcher in security and privacy for e-health and smart wearables. The position is funded by Holistics, a 7.4 million research project supported by the Disruptive Technologies Innovation Fund. Holistics focuses on smart human sensing for health, aging and wellness. The Post-Doctoral Researcher will investigate how to achieve privacy-preserving computation of medical and physiological information collected by wearables and other sensors. In particular, the research will focus on cryptographic protocols and privacy enhancing technologies, in order to provide data and communication security, as well as blockchain technology, to provide traceability and user control.
The researcher is expected to have a PhD, and a track record of publications in the areas of security, privacy or cryptography. Previous experience in e-health and wearable security is welcome, but not required. The Post-Doctoral Researcher will work under the supervision of Dr. Paolo Palmieri, and will collaborate with other members of the team working on security and privacy, including a number of PhD students. Funding is available for 1 year, with an end date of August 2022. Funding for travel and research costs is also available. The start date is flexible, but early availability is an asset.

Deadline for applications: 25-Jun-2021 12:00 (noon) Irish time

Closing date for applications:

Contact: For informal discussion please contact Dr. Paolo Palmieri at p.palmieri@cs.ucc.ie
Applications must be submitted by the deadline on the university HR portal (select Job ID no. 046751): https://ore.ucc.ie/pls/corerecruit/

More information: https://my.corehr.com/pls/uccrecruit/erq_jobspec_version_4.display_form?p_company=5023&p_internal_external=E&p_display_in_irish=N&p_applicant_no=&p_recruitment_id=046751&p_process_type=&p_form_profile_detail=&p_display_apply_ind=Y&p_refresh_search=Y

The Computer Science Department at Université libre de Bruxelles is seeking to recruit several teaching assistants. These half teaching / half research PhD positions are for three years, usually renewable for another three years. PhD salaries in Belgium are very competitive.

Teaching assistants will perform high-quality research under the supervision of one professor from the Department in order to obtain a PhD degree. Possible research topics include any area of cryptography, particularly applied, post-quantum and mathematical cryptography. Cryptography researchers affiliated with ULB include Liran Lerman, Olivier Markowitch, Christophe Petit and Gilles Van Assche

Main requirements:
- master degree in computer science or a cognate discipline
- sufficient knowledge of French to teach at undergraduate level

More information here: http://wwwdev.ulb.ac.be/greffe/files/7311.pdf

For informal inquiries, particularly related to post-quantum and mathematical cryptography, please contact Christophe Petit (first name dot last name at ulb dot be)

Closing date for applications:

Contact: Christophe Petit

More information: http://wwwdev.ulb.ac.be/greffe/files/7311.pdf

We examine Multi-Party Computation protocols in the active-security-with-abort setting for $Q_2$ access structures over small and large finite fields $F_p$ and over rings $Z_{p^k}$. We give general protocols which work for any $Q_2$ access structure which is realised by a multiplicative Extended Span Program. We generalize a number of techniques and protocols from various papers and compare the different methodologies. In particular we examine the expected communication cost per multiplication gate when the protocols are instantiated with different access structures.

We investigate *all* NIST PQC Round~3 KEM candidates from the viewpoint of fault-injection attacks: Classic McEliece, Kyber, NTRU, Saber, BIKE, FrodoKEM, HQC, NTRU Prime, and SIKE. All KEM schemes use variants of the Fujisaki-Okamoto transformation, so the equality test of re-encryption in decapsulation is critical.

We survey effective key-recovery attacks if we can skip the equality test. We found the existing key-recovery attacks against Kyber, NTRU, Saber, FrodoKEM, HQC, one of two KEM schemes in NTRU Prime, and SIKE. We propose a new key-recovery attack against the other KEM scheme in NTRU Prime. We also report an attack against BIKE that leads to leakage of information of secret keys.

The open-source pqm4 library contains all KEM schemes except Classic McEliece and HQC. We show that giving a single instruction-skipping fault in the decapsulation processes leads to skipping the equality test *virtually* for Kyber, NTRU, Saber, BIKE, and SIKE. We also report the experimental attacks against them. We also report the implementation of NTRU Prime allows chosen-ciphertext attacks freely and the timing side-channel of FrodoKEM reported in Guo, Johansson, and Nilsson (CRYPTO 2020) remains.

From June 2019 to March 2020, IETF conducted a selection process to choose password authenticated key exchange (PAKE) protocols for standardization. Similar standardization efforts were conducted before by IEEE (P1362.2) and ISO/IEC (11770-4). An important hallmark for this IETF selection process is its openness: anyone can nominate any candidate; all reviews are public; all email discussions on the IETF mailing lists are archived and publicly readable. However, despite the openness, it is unclear whether this IETF selection process has presented a successful model. Several important questions that were raised during the selection process had remained unaddressed even after the two winners (CPace and OPAQUE) were announced. We reflect on the IETF PAKE selection process as a case study, and summarize lessons in a set of principles with the hope to improve security standardization in the future.

Well-known authentication mechanisms such as Public-key Infrastructure (PKI) and Identity-based Public-key Certificates (ID-PKC) are not suitable to integrate with the peer-to-peer (P2P) network environment. The reason is the difficulty in maintaining a centralized authority to manage the certificates. The authentication becomes even harder in an anonymous environment. We present three authentication protocols such that the users can authenticate themselves in an anonymous P2P network, without revealing their identities. Firstly, we propose a way to use existing ring signature schemes to obtain anonymous authentication. Secondly, we propose an anonymous authentication scheme utilizing secret sharing schemes. Finally, we propose a zero-knowledge-based anonymous authentication protocol. We provide security justifications of the three protocols in terms of anonymity, completeness, soundness, resilience to impersonation attacks, and resilience to replay attacks.

One of the finalists in the NIST post-quantum cryptography competition is the Classic McEliece cryptosystem. Unfortunately, its public key size represents a practical limitation. One option to address this problem is to use different families of error-correcting codes. Most of such attempts failed as those cryptosystems were proved not secure. In this paper, we propose a McEliece type cryptosystem using high minimum distance self-dual codes and punctured codes derived from them. To the best of our knowledge, such codes have not been implemented in a code-based cryptosystem until now. For the 80-bit security case, we construct an optimal self-dual code of length 1\,064, which, as far as we are aware, was not presented before. Compared to the original McEliece cryptosystem, this allows us to reduce the key size by about 38.5\%.

General-purpose zero-knowledge proofs for all \textsf{NP} languages greatly simplify secure protocol design. However, they inherently require the code of the underlying relation. If the relation contains black-box calls to a cryptographic function, the code of that function must be known to use the ZK proof, even if both the relation and the proof require only black-box access to the function. Rosulek (Crypto'12) shows that non-trivial proofs for even simple statements, such as membership in the range of a one-way function, require non-black-box access.

We propose an alternative approach to bypass Rosulek's impossibility result. Instead of asking for a ZK proof directly for the given one-way function $f$, we seek to construct a \textit{new} one-way function $F$ given only black-box access to $f$, \textit{and} an associated ZK protocol for proving non-trivial statements, such as range membership, over its output. We say that $F$, along with its proof system, is a \textit{proof-based} one-way function. We similarly define proof-based versions of other primitives, specifically pseudo-random generators and collision-resistant hash functions.

We show how to construct proof-based versions of each of the primitives mentioned above from their ordinary counterparts under mild but necessary restrictions over the input. More specifically,

- We first show that if the prover entirely chooses the input, then proof-based pseudo-random generators cannot be constructed from ordinary ones in a black-box manner, thus establishing that some restrictions over the input are necessary.

- We next present black-box constructions handling inputs of the form $(x,r)$ where $r$ is chosen uniformly by the verifier. This is similar to the restrictions in the widely used Goldreich-Levin theorem. The associated ZK proofs support range membership over the output as well as arbitrary predicates over prefixes of the input.

Our results open up the possibility that general-purpose ZK proofs for relations that require black-box access to the primitives above may be possible in the future without violating their black-box nature by instantiating them using proof-based primitives instead of ordinary ones.

Secure Multiparty Computation (MPC) is an invaluable tool for training machinelearning models when the training data cannot be directly accessed by the modeltrainer. Unfortunately, complex algorithms, such as deep learning models, havetheir computational complexities increased by orders of magnitude when performedusing MPC protocols. In this contribution, we study how to efficiently train animportant class of machine learning problems by using MPC where features areknown by one of the computing parties and only the labels are private. We proposenew protocols combining differential privacy (DP) and MPC in order to privatelyand efficiently train a deep learning model in such scenario. More specifically, werelease differentially private information during the MPC computation to dramat-ically reduce the training time. All released information idoes not compromisethe privacy of the labels at the individual level. Our protocols can have runningtimes that are orders of magnitude better than a straightforward use of MPC at amoderate cost in model accuracy.