International Association
for Cryptologic Research

We present the first natural ${\mathsf{NP}}$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is equivalent to mild average-case hardness of this $\mathsf{NP}$-complete problem. The problem, which originated in the 1960s, is the Conditional Time-Bounded Kolmogorov Complexity Problem: let $K^t(x \mid z)$ be the length of the shortest ``program'' that, given the ``auxiliary input'' $z$, outputs the string $x$ within time $t(|x|)$, and let ${\mathsf{McKTP}}[t,\zeta]$ be the set of strings $(x,z,k)$ where $|z| = \zeta(|x|)$, $|k| = \log |x|$ and $K^t(x \mid z)< k$, where, for our purposes, a ``program'' is defined as a RAM machine.

Our main results shows that for every polynomial $t(n)\geq n^2$, there exists some polynomial $\zeta$ such that $\mathsf{McKTP}[t,\zeta]$ is $\mathsf{NP}$-complete. We additionally observe that the result of Liu-Pass (FOCS'20) extends to show that for every polynomial $t(n)\geq 1.1n$, and every polynomial $\zeta(\cdot)$, mild average-case hardness of $\mathsf{McKTP}[t,\zeta]$ is equivalent to the existence of OWFs.

Functional encryption generates sophisticated keys for users so that they can learn specific functions of the encrypted message. We provide a generic construction of chosen ciphertext attacks (CCA) secure public-key functional encryption (PKFE) for all polynomial-size circuits. Our PKFE produces succinct ciphertexts that are independent of the size and depth of the circuit class under consideration.

We accomplish our goal in two steps. First, we define a new cryptographic tool called constrained witness pseudorandom function (CWPRF) which is motivated by combining WPRF of Zhandry (TCC 2016) and constrained PRF of Boneh and Waters (ASIACRYPT 2013). More specifically, CWPRF computes pseudorandom values associated with NP statements and generates constrained keys for boolean functions. We can recompute the pseudorandom value corresponding to a particular statement either using a public evaluation key with a valid witness for the statement or applying a constrained key for a function that satisfies the statement. We construct CWPRF by coupling indistinguishability obfuscation (iO) and CPRF supporting all polynomial-size functions. In the second and main technical step, we show a generic construction of a CCA secure PKFE for all circuits utilizing our CWPRF. It has been observed that obtaining PKFE supporting all circuits is already a complex task and iO-based constructions of PKFEs are only proven to be chosen plaintext attacks (CPA) secure. On the other hand, existing CCA secure functional encryption schemes are designed for specific functions such as equality testing, membership testing, linear function etc. We emphasize that our construction presents the first CCA secure PKFE for all circuits along with succinct ciphertexts.

In this paper we show that a wide class of (computationally) special-sound proofs of knowledge which have unique response property and are standard-model zero-knowledge are weak simulation-extractable when made non-interactive by the Fiat--Shamir transform. We prove that two efficient updatable universal zkSNARKs---Plonk (Gabizon et al. 19) and Sonic~(Maller et al. 19)---meet these requirements and conclude by showing their weak simulation-extractability. As a side result we also show that relying security on rewinding and Fiat--Shamir transform often comes at a great price of inefficient (yet still polynomial time) knowledge extraction and the security loss introduced by these techniques should always be taken into account.

A signer and message ambiguous signature enables a recipient to request a signer to sign a sensible message such that the signer cannot guess what message he signed and the receiver cannot deduce the signer's identity. In this work, we formalize this type of signature, introduce the corresponding security requirements and describe two instantions. The first one assumes that the signer hides his identity in $n$ independently generated public keys, while the second one assumes that all $n$ public keys share the same public parameters.

Haber and Pinkas discussed the principle of when it is secure to reuse key material between public-key cryptosystems. They showed that this can be secure for multiple combinations of systems, including Schnorr signatures. Degabriele, Lehmann, Paterson, Smart and Strefler proved the security of sharing a key pair between a generic elliptic curve Schnorr signature scheme and an elliptic curve Diffie-Hellman based KEM in the random oracle model (ROM). They essentially ran the original security proofs in parallel by leveraging domain separation for the random oracle (RO) usage between the signature scheme and the specific KDF of the KEM. We make two contributions. First, we extend the result in Degabriele et al. by proving the joint security in the ROM of an X25519 based KEM with an HKDF-Extract-like KDF construction and Ed25519. Second, we make no assumptions about domain separation of RO usage between the two systems while making minimal assumptions about the format of the RO usage in Ed25519. Our result is applicable to Ed448 and a corresponding KEM based on X448 as well.

Fully Homomorphic encryption (FHE) has been gaining popularity as an emerging way of enabling an unlimited number of operations on the encrypted message without decryption. A major drawback of FHE is its high computational cost. Especially, a bootstrapping that refreshes the noise accumulated through consequent FHE operations on the ciphertext is even taking minutes. This significantly limits the practical use of FHE in numerous real applications. By exploiting massive parallelism available in FHE, we demonstrate the first GPU implementation for bootstrapping CKKS, one of the most promising FHE schemes that support arithmetic of approximate numbers. Through analyzing FHE operations, we discover that the major performance bottleneck is their high main-memory bandwidth requirement, which is exacerbated by leveraging existing optimizations targeted to reduce computation. These observations lead us to extensively utilize memory-centric optimizations such as kernel fusion and reordering primary functions. Our GPU implementation shows a 7.02x speedup for a single FHE-multiplication compared to the state-of-the-art GPU implementation and 0.423us of amortized bootstrapping time per bit, which corresponds to a speedup of 257x over a single-threaded CPU implementation. By applying this to a logistic regression model training, we achieved a 40.0x speedup compared to the previous 8-thread CPU implementation with the same data.

This paper promotes and continues a research program aimed at proving the security of block ciphers such as AES against important and well-studied classes of attacks. In particular, we initiate the study of (almost) $t$-wise independence of concrete block-cipher construction paradigms such as substitution-permutation networks and key-alternating ciphers. This is a meaningful target, as sufficiently strong (almost) pairwise independence already suffices to resist (truncated) differential attacks and linear cryptanalysis. Our results are two-fold.

- Our first result concerns substitution-permutation networks (SPNs) that model block ciphers such as AES. We prove the almost pairwise-independence of an SPN instantiated with a concrete S-box such as the patched inverse function $x \mapsto x^{-1}$ as well as an appropriate linear mixing layer, given sufficiently many rounds and independent sub-keys. Our proof relies on a characterization of S-box computation on input differences in terms of sampling output differences from certain sub-spaces, and a new randomness extraction lemma (which we prove with Fourier-analytic techniques) that establishes when such sampling yields uniformity. We use our techniques in particular to prove almost pairwise-independence for sufficiently many AES rounds, assuming independent sub-keys.

- Secondly, we show that instantiating a key-alternating cipher (which can be thought of as a degenerate case of SPNs) with most permutations gives us (almost) $t$-wise independence in $t + o(t)$ rounds. In order to do this, we use the probabilistic method to develop two new lemmas, an independence-amplification lemma and a distance amplification lemma, that allow us to reason about the evolution of key-alternating ciphers.

Although isogeny-based cryptographic schemes enjoy the lowest key sizes amongst current post-quantum cryptographic candidates, they unfortunately come at a high computational cost, which makes their deployment on the ever-growing number of resource-constrained devices difficult. Speeding up the expensive post-quantum cryptographic operations by delegating these computations from a weaker client to untrusted powerful external servers is a promising approach. Following this, we present in this work mechanisms allowing computationally restricted devices to securely and verifiably delegate isogeny computations to potentially untrusted third parties. In particular, we propose two algorithms that can be seamlessly integrated into existing isogeny-based protocols and which lead to a much lower cost for the delegator than the full, local computation. For example, we reduce the public-key computation step of SIDH/SIKE to about 11% of the local computation cost, and the zero-knowledge proof of identity from Jao and De Feo to about 4% for the prover and almost free for the verifier, respectively, at the NIST security level 1.

We are offering Ph.D. programs in Computer Science and Mathematics, in collaboration with Ramakrishna Mission Vivekananda Educational and Research Institute (RKMVERI), India.

Research Area: Our current Research focus includes Cryptography, Quantum Computing, Cyber Security, Mathematics and its Applications, Machine Learning, and Artificial Intelligence.

Eligibility: All students passed or in their final semester pursuing M.Tech / M.E / M.Stat / M.Math / M.Sc or equivalent degree in Computer Science, Information Technology, Electronics, Mathematics, Data Science, Statistics or other areas of quantitative sciences may apply.

Fellowship: All successful candidates will be offered a TCG CREST fellowship of Rupees Sixty Thousand (60,000.00 INR) per month. Also, a contingency grant of up to Two Lacs (2,00,000.00 INR) will be awarded per annum.

Admission Process: The online application process for Ph.D. admission is open and will be valid up to 17th May 2021. Interested candidates are requested to apply online by filling up the application form provided on the admission page (the link is given below). All other necessary details are also available therein.

Admission Page: https://www.tcgcrest.org/announcements/iai-phd-programme-2021/

Closing date for applications:

Contact: Nilanjan Datta

More information: https://www.tcgcrest.org/announcements/iai-phd-programme-2021/

WE PROPOSE:

A Contractual Agent position FG IV in Ispra, Italy. 36 months initial contract with possible renewals up to maximum 6 years. The successful candidate will contribute to the activities of the unit aiming at strengthening the citizen’ security and privacy by exploring innovative forensic technologies to support the fight against organised crimes.

He/she will conduct scientific and technical studies in the area of cybersecurity and fight against cyber-dependent crime domains to support the new strategic agenda 2019-2024 and its first priority: Protecting citizens and freedoms.

ELIGIBILITY:

To be eligible for the position, the candidate must be on a valid EPSO reserve list for Function Group IV contract staff.

Candidates who are on a valid EPSO reserve list or have applied to an EPSO selection procedure can apply to this specific position through http://recruitment.jrc.ec.europa.eu/?type=AX.

WE LOOK FOR:

The candidate shall have a PhD degree - or a minimum of 5 years of full-time research or working experience after the first University degree giving access to PhD studies in the field of applied mathematics, cryptography, computer science, or machine learning and deep learning techniques, or similar.

Solid knowledge and experience are required in:

• Mathematics and more particularly cryptography or multi-linear algebra;
• Machine learning and deep learning;
• Ability to work in a multilingual and multicultural environment;
• English language, at least C1 level both oral and written.

The following knowledge or experience are an asset:

• Experience with digital forensic techniques;
• Experience with High-Performance Computing platform;
• Good knowledge of programming languages such as C/C++/C#, Python, MATLAB;
• Knowledge of quantum programming and simulation;
• Knowledge of machine learning libraries such as OpenCV, libSVM, Tenfosorflow/Theano/Keras;
• Relevant publications in peer-reviewed journals and international security conferences;

Closing date for applications:

Contact:

How to apply to an EPSO selection procedure? Apply either to the permanent EPSO call https://epso.europa.eu/documents/2240_en or a specialised call for researchers https://ec.europa.eu/jrc/en/working-with-us/jobs/vacancies/function-group-IV-researchers

laurent.beslay@ec.europa.eu

More information: https://recruitment.jrc.ec.europa.eu/showprj.php?type=A&id=1961

Billions of connected devices are in use nowadays, including smartphones, media tablets, laptop and desktop computers, automotive electronic control units, smart sensors, smart cards, etc. To guarantee the confidentiality, the integrity and the authenticity of their sensitive data, various security mechanisms have been specified, and some of them mathematically proved to be secure, particularly against linear cryptanalysis and differential cryptanalysis. However, implementing them on a digital circuit without introducing vulnerability still remains a challenge.

The most exploited vulnerabilities are implementation bugs, as well as side channels, which leak information such as the execution time of a sensitive operation. The two vulnerability classes can also be combined: for instance, Meltdown (CVE-2017-5754) and Spectre (CVE-2017-5753) simultaneously exploit a hardware bug and a measure of the data cache access time.

Since 2016, artificial intelligence, and more precisely deep learning using neural networks, has been used to evaluate the resistance level of countermeasures against side-channel attack. Thus, an AES implementation protected by secret sharing based on Boolean masking has been shown insecure, as well as desynchronization, two countermeasures yet known to be very effective. Regarding public key cryptography, some vulnerabilities have also been identified in RSA implementations protected by blinding of the message, of the secret exponent and/or of the modulo.

Artificial intelligence is therefore a valuable aid in identifying vulnerabilities, the use of which has to be extended, to algorithms other than AES and RSA, but above all to other countermeasures such as register randomization, internal state randomization, modular operation re-randomization, etc. This is the first objective of the thesis. Additionally, although already very effective, it seems possible to further improve analyzes by neural networks, by using several intermediate values, and/or several side channels (time, electromagnetic radiation, etc.). This is the second objective of the thesis.

Closing date for applications:

Contact: Laurent Sauvage

More information: https://www.adum.fr/as/ed/voirproposition.pl?langue=&site=TelecomPT&matricule_prop=36276

We are looking for a motivated, bright, and hard-working student that wishes to pursue a PhD in Cryptography. The candidate will work in cryptographic research topics such as zero-knowledge arguments, oblivious algorithms, trusted-hardware-assisted cryptography, verifiable computation, homomorphic commitments, searchable encryption, secure blockchain protocols, and more. The specific research topic will be determined based on the common interests of the candidate and the supervisor.

Applicants’ profile

• MSc or BSc degree in Computer Science or related field.
• Excellent programming skills, preferably in C++.
• Very good understanding of CS fundamentals: algorithm analysis, data structures, etc.
• Good understanding of basic cryptographic primitives: hashing, encryption, commitments, etc.
• Strong enthusiasm about research.

Ideal candidates have prior knowledge in implementing cryptographic primitives or a relevant project. Solid background in theoretical computer science (complexity analysis, reduction proofs, etc.), or experience in programming for trusted-hardware environments (Intel SGX, ARM TrustZone, etc.) is also a big plus.

Work environment
HKUST offers guaranteed funding for the PhD duration with competitive stipends. Our CSE department was ranked 17th in the world in 2020 by THE World University Rankings. Our graduates typically produce research output of the highest quality and consistently staff world-class institutions. The lab offers a creative work environment that is ideal for excellent research.

Closing date for applications:

Contact: Dimitrios Papadopoulos

We are looking for a highly motivated candidate to fill a post-doctoral researcher position at Northwestern University in applied cryptography. Topics include:

• Secure multi-party computation
• Zero-knowledge proof
• Post-quantum security
• Differential privacy
• Other related/non-related topics of mutual interests

Experience in implementation is preferred.

Apply: please send your CV (and other material if available) to the PoC.

Closing date for applications:

Contact: Xiao Wang (wangxiao1254@gmail.com)

Event date: 14 November 2021
Submission deadline: 25 June 2021
Notification: 13 August 2021

Event date: 8 November 2021

In TCC 2013, Boyen suggested the first lattice based construction of attribute based encryption (ABE) for the circuit class $NC1$. Unfortunately, soon after, a flaw was found in the security proof of the scheme. However, it remained unclear whether the scheme is actually insecure, and if so, whether it can be repaired. Meanwhile, the construction has been heavily cited and continues to be extensively studied due to its technical novelty. In particular, this is the first lattice based ABE which uses linear secret sharing schemes (LSSS) as a crucial tool to enforce access control.

In this work, we show that the scheme is in fact insecure. To do so, we provide a polynomial-time attack that completely breaks the security of the scheme. We suggest a route to fix the security of the scheme, via the notion of admissible linear secret sharing schemes (LSSS) and instantiate these for the class of DNFs. Subsequent to our work, Datta, Komargodski and Waters (Eurocrypt 2021) provided a construction of admissible LSSS for NC1 and resurrected Boyen's claimed result.

Let n be a positive integer. An n-stage Galois NFSR has n registers and each register is updated by a feedback function. Then a Galois NFSR is called nonsingular if every register generates (strictly) periodic sequences, i.e., no branch points. In this paper, a generic method for investigating nonsingular Galois NFSRs is provided. Two fundamental concepts that are standard Galois NFSRs and the simplified feedback function of a standard Galois NFSR are proposed. Based on the new concepts, a sufficient condition is given for nonsingular Galois NFSRs. In particular, for the class of Galois NFSRs with linear simplified feedback functions, a necessary and sufficient condition is presented. Hopefully, some new insights are provided on determining nonsingular Galois NFSRs.

Multiparty computation does not tolerate $n/3$ corruptions under a plain asynchronous communication network, whatever the computational assumptions. However, Beerliová-Hirt-Nielsen [BHN, Podc'10] showed that, assuming access to a synchronous broadcast at the beginning of the protocol, enables to tolerate up to $t<n/2$ corruptions. This model is denoted as ``Almost asynchronous'' MPC. Yet, [BHN] suffers from limitations: (i) {Setup assumptions:} their protocol is based on an encryption scheme, with homomorphic additivity, such that the secret keys of players are given by a trusted entity ahead of the protocol. It was left as an open question in [BHN] whether one can remove this assumption, denoted as ``trusted setup''. (ii) {Common Randomness generation:} the generation of common random secrets uses the broadcast, therefore is allowed only at the beginning of the protocol. (iii) {Proactive security:} the previous limitation directly precludes the possibility of tolerating a mobile adversary. Indeed, tolerance to this kind of adversary, which is denoted as ``proactive'' MPC, would require a mechanism by which players refresh their (shares of) keys, without the intervention of a trusted entity, with {on the fly} randomness generation. (iv) {Triple generation latency: } The protocol to preprocess the material necessary for multiplication has latency $t$, which is thus linear in the number of players.

We remove all the previous limitations. Of independent interest, our novel computation framework revolves around players, denoted as ``kings'', which, in contrast to Podc'10, are now \emph{replaceable} after every elementary step of the computation.

Revocable hierarchical identity-based encryption (RHIBE) is an extension of HIBE that provides the efficient key revocation function by broadcasting an update key per each time period. Many RHIBE schemes have been proposed by combining an HIBE scheme and the tree-based revocation method, but a generic method for constructing an RHIBE scheme has not been proposed. In this paper, we show for the first time that it is possible to construct RHIBE schemes by generically combining underlying cryptographic primitives and tree-based revocation methods. We first generically construct an RHIBE-CS scheme by combining HIBE scheme and the complete subtree (CS) method, and prove the adaptive security of this scheme by using the adaptive security of the HIBE schemes. Next, we generically construct an RHIBE-SD scheme by combining HIBE and hierarchical single revocation encryption (HSRE) schemes, and the subset difference (SD) method to reduce the size of an update key. Finally, we generically construct an RHIBE-CS scheme with shorter ciphertexts by combining HIBE schemes with constant-size ciphertext and the CS method.

Cryptocurrencies have received a lot of research attention in recent years following the release of the first cryptocurrency Bitcoin. With the rise in cryptocurrency transactions, the need for smart contracts has also increased. Smart contracts, in a nutshell, are digitally executed contracts wherein some parties execute a common goal. The main problem with most of the current smart contracts is that there is no privacy for a party's input to the contract from either the blockchain or the other parties. Our research builds on the Hawk project that provides transaction privacy along with support for smart contracts. However, Hawk relies on a special trusted party known as a manager, which must be trusted not to leak each party's input to the smart contract. In this paper, we present a practical private smart contract protocol that replaces the manager with an MPC protocol such that the function to be executed by the MPC protocol is relatively lightweight, involving little overhead added to the smart contract function, and uses practical sigma protocols and homomorphic commitments to prove to the blockchain that the sum of the incoming balances to the smart contract matches the sum of the outgoing balances.