International Association
for Cryptologic Research

Functional encryption (FE) is a new paradigm of public key encryption that can control the exposed information of plaintexts by supporting computation on encrypted data. In this paper, we propose efficient multi-client FE (MCFE) schemes that compute the set intersection of ciphertexts generated by two clients. First, we propose an MCFE scheme that calculates the set intersection cardinality (MCFE-SIC) and prove its static security under dynamic assumptions. Next, we extend our MCFE-SIC scheme to an MCFE scheme for set intersection (MCFE-SI) and prove its static security under dynamic assumptions. The decryption algorithm of our MCFE-SI scheme is more efficient than the existing MCFE-SI scheme because it requires fewer pairing operations to calculate the intersection of two clients. Finally, we propose a decentralized MCFE scheme for set intersection (DMCFE-SI) that decentralizes the generation of function keys. Our MCFE schemes can be effectively applied to a privacy-preserving contact tracing system to prevent the spread of recent infectious diseases.

Real-world random number generators (RNGs) cannot afford to use (slow) cryptographic hashing every time they refresh their state $R$ with a new entropic input $X$. Instead, they use ``superefficient'' simple entropy-accumulation procedures, such as $$R \leftarrow \mathsf{rot}_{\alpha, n}(R) \oplus X,$$ where $\mathsf{rot}_{\alpha,n}$ rotates an $n$-bit state $R$ by some fixed number $\alpha$. For example, Microsoft's RNG uses $\alpha=5$ for $n=32$ and $\alpha=19$ for $n=64$. Where do these numbers come from? Are they good choices? Should rotation be replaced by a better permutation $\pi$ of the input bits?

In this work we initiate a rigorous study of these pragmatic questions, by modeling the sequence of successive entropic inputs $X_1,X_2,\ldots$ as independent (but otherwise adversarial) samples from some natural distribution family ${\mathcal D}$. Our contribution is as follows.

* We define $2$-monotone distributions as a rich family ${\mathcal D}$ that includes relevant real-world distributions (Gaussian, exponential, etc.), but avoids trivial impossibility results.

* For any $\alpha$ with $\gcd(\alpha,n)=1$, we show that rotation accumulates $\Omega(n)$ bits of entropy from $n$ independent samples $X_1,\ldots,X_n$ from any (unknown) $2$-monotone distribution with entropy $k > 1$.

* However, we also show that some choices of $\alpha$ perform much better than others for a given $n$. E.g., we show $\alpha=19$ is one of the best choices for $n=64$; in contrast, $\alpha=5$ is good, but generally worse than $\alpha=7$, for $n=32$.

* More generally, given a permutation $\pi$ and $k\ge 1$, we define a simple parameter, the covering number $C_{\pi,k}$, and show that it characterizes the number of steps before the rule $$(R_1,\ldots,R_n)\leftarrow (R_{\pi(1)},\ldots, R_{\pi(n)})\oplus X$$ accumulates nearly $n$ bits of entropy from independent, $2$-monotone samples of min-entropy $k$ each.

* We build a simple permutation $\pi^*$, which achieves nearly optimal $C_{\pi^*,k}\approx n/k$ for all values of $k$ simultaneously, and experimentally validate that it compares favorably with all rotations $\mathsf{rot}_{\alpha,n}$.

In 2018, the longest vector problem and closest vector problem in local fields were introduced, as the p-adic analogues of the shortest vector problem and closest vector problem in lattices of Euclidean spaces. They are considered to be hard and useful in constructing cryptographic primitives, but no applications in cryptography were given. In this paper, we construct the first signature scheme and public-key encryption cryptosystem based on p-adic lattice by proposing a trapdoor function with the orthogonal basis of p-adic lattice. These cryptographic schemes have reasonable key size and efficiency, which shows that p-adic lattice can be a new alternative to construct cryptographic primitives and well worth studying.

Secure multi-party computation (MPC) allows multiple parties to securely evaluate a public function on their private inputs. The field has steadily moved forward and real-world applications have become practical. However, MPC implementations are often hand-built and require cryptographic knowledge. Thus, special compilers like HyCC (Büscher et al., CCS'18) have been developed, which automatically compile high-level programs to combinations of Boolean and arithmetic circuits required for mixed-protocol (hybrid) MPC. In this work, we explore the advantages of extending MPC compilers with an intermediate representation (IR) as commonly used in modern compiler infrastructures. For this, we extend HyCC with a graph-based IR that facilitates the implementation of well-known algorithms from compiler design as well as further MPC-specific optimizations. We demonstrate the benefits by implementing arithmetic decomposition based on our new IR that automatically extracts arithmetic expressions and then compiles them into separate circuits. For a line intersection algorithm, we require 40% less run-time and improve total communication by a factor of 3x compared to regular HyCC when securely evaluating the corresponding circuit with the hybrid MPC framework ABY (Demmler et al., NDSS'15).

One of the most important verifiability techniques for mix nets is randomized partial checking (RPC). This method is employed in a number of prominent secure e-voting systems, including Pret a Voter, Civitas, and Scantegrity II, some of which have also been used for real political elections including in Australia.

Unfortunately, it turned out that there exists a significant gap between the intended and the actual verifiability tolerance of the original RPC protocol. This mismatch affects exactly the "Achilles heel" of RPC, namely those application scenarios where manipulating a few messages can swap the final result (e.g., in close runoff elections).

In this work, we propose the first RPC protocol which closes the aforementioned gap for decryption mix nets. We prove that our new RPC protocol achieves an optimal verifiability level, without introducing any disadvantages. Current implementations of RPC for decryption mix nets, in particular for real-world secure e-voting, should adopt our changes to improve their security.

Most recently, Izza et al. propose a new ECC-based RFID authentication protocol by showing the vulnerabilities of Naeem's protocol. They claim that their scheme provides security and privacy. However, we assert that their protocol does not satisfy privacy including anonymity, untraceability, forward and backward secrecy on the contrary of their claim. We also argue that the scheme suffers from availability problems.

Custodian service is a service safeguarding a firm's or individual's financial assets or secret information. Such services often present a user with security versus ownership dilemma. The user does not wish to pass full control over their asset to the custodian to facilitate safeguarding. A control sharing mechanism allowing the custodian to hold enough information and keeping the user as the owner of the asset is required. For the assets being secret information, cryptographic protocols addressing this dilemma are known as prepositioned secret sharing~(PSS) protocols. PSS schemes distinguish redundant ``common'' shares and specific ``activating'' shares controlling the very possibility of the secret information reconstruction. Usually, PSS schemes: 1) lack robustness with respect to the amount of ``common'' shares, i.e., a high redundancy degree in ``common'' enables them to reconstruct the secret without ``activation'', and 2) are inflexible in configuring the robustness of the ``activating'' shares, i.e., how many ``activating'' shares can be lost or stolen before the secret can be reconstructed. In this paper, we present a PSS addressing these shortcomings.

Let $\mktp[s]$ be the set of strings $x$ such that $K^t(x) \leq s(|x|)$, where $K^t(x)$ denotes the $t$-bounded Kolmogorov complexity of the truthtable described by $x$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every $\varepsilon>0$, polynomial $t(n) \geq (1+\varepsilon)n$, and every ``nice'' class $\F$ of super-polynomial functions, the following are equivalent: - the existence of some function $T \in \F$ such that $T$-hard one-way functions (OWF) exists (with non-uniform security); - the existence of some function $T \in \F$ such that $\mktp[T^{-1}]$ is mildly average-case hard with respect to sublinear-time non-uniform algorithms (with running-time $n^{\delta}$ for some $0<\delta<1$). For instance, existence of subexponentially-hard (resp. quasi-polynomially-hard) OWFs is equivalent to mild average-case hardness of $\mktp[\poly\log n]$ (resp. $\mktp[2^{O(\sqrt{\log n})})]$) w.r.t. sublinear-time non-uniform algorithms.

We additionally note that if we want to deduce $T$-hard OWFs where security holds w.r.t. uniform $T$-time probabilistic attackers (i.e., uniformly-secure OWFs), it suffices to assume sublinear time hardness of $\mktp$ w.r.t. uniform probabilistic sublinear-time attackers. We complement this result by proving lower bounds that come surprisingly close to what is required to unconditionally deduce the existence of (uniformly-secure) OWFs: $\mktp[\poly\log n]$ is worst-case hard w.r.t. uniform probabilistic sublinear-time algorithms, and $\mktp[n-\log n]$ is mildly average-case hard for all $O(t(n)/n^3)$-time deterministic algorithms.

ECIES has been widely used in many cryptographic devices and systems to ensure the confidentiality of communication data. Hence, researching its security of implementation is essential. It is generally considered that the embedded point validation towards the input point $Q$ during decryption is enough to resist most of the existing fault attacks and small subgroup attacks. Even many open source algorithm libraries (e.g., OpenSSL and BouncyCastle) only employ the embedded point validation to resist fault attack. However, the proposed weak curve fault attack in this paper can break this situation because it can successfully pass the embedded point validation and the validation of the scalar multiplication about the input point $Q$ and cofactor $h$(i.e., $hQ \ne \mathcal{O}$). Moreover, the proposed attack does not require that the instances of ECDLP on the weak curve derived by fault injection is computationally practical which could increase the availability of fault injection. The simulations demonstrate the feasibility of our attack. Finally, we also investigate the implementations of $14$ open source algorithm libraries, and there are $10$ algorithm libraries which can not block our attack. Hence, we also give some suggestions about countermeasures.

Revocable hierarchical identity-based encryption (RHIBE) is an extension of hierarchical identity-based encryption (HIBE) supporting the key revocation mechanism. In this paper, we propose a generic construction of RHIBE from HIBE with the complete subtree method. Then, we obtain the first RHIBE schemes under the quadratic residuosity assumption, CDH assumption without pairing, factoring Blum integers, LPN assumption, and code-based assumption, and the first almost tightly secure RHIBE schemes under the k-linear assumption. Furthermore, by using pairing-based (dual) identity-based broadcast encryption, we obtain the variants of the scheme with shorter ciphertexts or shorter key updates.

We provide the first constructions of non-interactive zero-knowledge and Zap arguments for NP based on the sub-exponential hardness of Decisional Diffie-Hellman against polynomial time adversaries (without use of groups with pairings).

Central to our results, and of independent interest, is a new notion of interactive trapdoor hashing protocols.

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/