## CryptoDB

### Charanjit S. Jutla

#### Affiliation: IBM Research

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

Shorter QA-NIZK and SPS with Tighter Security
Abstract

Quasi-adaptive non-interactive zero-knowledge proof (QA-NIZK) systems and structure-preserving signature (SPS) schemes are two powerful tools for constructing practical pairing-based cryptographic schemes. Their efficiency directly affects the efficiency of the derived advanced protocols.We construct more efficient QA-NIZK and SPS schemes with tight security reductions. Our QA-NIZK scheme is the first one that achieves both tight simulation soundness and constant proof size (in terms of number of group elements) at the same time, while the recent scheme from Abe et al. (ASIACRYPT 2018) achieved tight security with proof size linearly depending on the size of the language and the witness. Assuming the hardness of the Symmetric eXternal Diffie-Hellman (SXDH) problem, our scheme contains only 14 elements in the proof and remains independent of the size of the language and the witness. Moreover, our scheme has tighter simulation soundness than the previous schemes.Technically, we refine and extend a partitioning technique from a recent SPS scheme (Gay et al., EUROCRYPT 2018). Furthermore, we improve the efficiency of the tightly secure SPS schemes by using a relaxation of NIZK proof system for OR languages, called designated-prover NIZK system. Under the SXDH assumption, our SPS scheme contains 11 group elements in the signature, which is shortest among the tight schemes and is the same as an early non-tight scheme (Abe et al., ASIACRYPT 2012). Compared to the shortest known non-tight scheme (Jutla and Roy, PKC 2017), our scheme achieves tight security at the cost of 5 additional elements.All the schemes in this paper are proven secure based on the Matrix Diffie-Hellman assumptions (Escala et al., CRYPTO 2013). These are a class of assumptions which include the well-known SXDH and DLIN assumptions and provide clean algebraic insights to our constructions. To the best of our knowledge, our schemes achieve the best efficiency among schemes with the same functionality and security properties. This naturally leads to improvement of the efficiency of cryptosystems based on simulation-sound QA-NIZK and SPS.

2018

PKC

Improved (Almost) Tightly-Secure Structure-Preserving Signatures
Abstract

Structure Preserving Signatures (SPS) allow the signatures and the messages signed to be further encrypted while retaining the ability to be proven valid under zero-knowledge. In particular, SPS are tailored to have structure suitable for Groth-Sahai NIZK proofs. More precisely, the messages, signatures, and verification keys are required to be elements of groups that support efficient bilinear-pairings (bilinear groups), and the signature verification consists of just evaluating one or more bilinear-pairing product equations. Since Groth-Sahai NIZK proofs can (with zero-knowledge) prove the validity of such pairing product equations, it leads to interesting applications such as blind signatures, group signatures, traceable signatures, group encryption, and delegatable credential systems.In this paper, we further improve on the SPS scheme of Abe, Hofheinz, Nishimaki, Ohkubo and Pan (CRYPTO 2017) while maintaining only an
$$O(\lambda )$$
O(λ)-factor security reduction loss to the SXDH assumption. In particular, we compress the size of the signatures by almost 40%, and reduce the number of pairing-product equations in the verifier from fifteen to seven. Recall that structure preserving signatures are used in applications by encrypting the messages and/or the signatures, and hence these optimizations are further amplified as proving pairing-product equations in Groth-Sahai NIZK system is not frugal. While our scheme uses an important novel technique introduced by Hofheinz (EuroCrypt 2017), i.e. structure-preserving adaptive partitioning, our approach to building the signature scheme is different and this leads to the optimizations mentioned. Thus we make progress towards an open problem stated by Abe et al. (CRYPTO 2017) to design more compact SPS-es with smaller number of group elements.

2018

TCC

Smooth NIZK Arguments
Abstract

We introduce a novel notion of smooth (-verifier) non- interactive zero-knowledge proofs (NIZK) which parallels the familiar notion of smooth projective hash functions (SPHF). We also show that the single group element quasi-adaptive NIZK (QA-NIZK) of Jutla and Roy (CRYPTO 2014) and Kiltz and Wee (EuroCrypt 2015) for linear subspaces can be easily extended to be computationally smooth. One important distinction of the new notion from SPHFs is that in a smooth NIZK the public evaluation of the hash on a language member using the projection key does not require the witness of the language member, but instead just requires its NIZK proof.This has the remarkable consequence that if one replaces the traditionally employed SPHFs with the novel smooth QA-NIZK in the Gennaro-Lindell paradigm of designing universally-composable password- authenticated key-exchange (UC-PAKE) protocols, one gets highly efficient UC-PAKE protocols that are secure even under adaptive corruption. This simpler and modular design methodology allows us to give the first single-round asymmetric UC-PAKE protocol, which is also secure under adaptive corruption in the erasure model. Previously, all asymmetric UC-PAKE protocols required at least two rounds. In fact, our protocol just requires each party to send a single message asynchronously. In addition, the protocol has short messages, with each party sending only four group elements. Moreover, the server password file needs to store only one group element per client. The protocol employs asymmetric bilinear pairing groups and is proven secure in the (limited programmability) random oracle model and under the standard bilinear pairing assumption SXDH.

2018

ASIACRYPT

Improved (Almost) Tightly-Secure Simulation-Sound QA-NIZK with Applications
Abstract

We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. In particular, under the SXDH assumption, the USS-QA-NIZK proof size is only seventeen group elements with a factor $$O(\log {Q})$$ loss in security reduction to SXDH. The USS-QA-NIZK primitive has many applications, including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs. We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications with (almost) tight-security to standard assumptions such as SXDH and, more generally, $$\mathcal{D}_k$$-MDDH. Thus, we get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.

2007

EPRINT

Utility Sampling for Trust Metrics in PKI
Abstract

We propose a new trust metric for a network of public key certificates, e.g. as in PKI, which allows a user to buy insurance at a fair price on the possibility of failure of the certifications provided while transacting with an arbitrary party in the network.
Our metric builds on a metric and model of insurance provided by Reiter and Stubblebine~\cite{RS}, while addressing various limitations and drawbacks of the latter. It conserves all the beneficial properties of the latter over other schemes, including protecting the user from unintentional or malicious dependencies in the network of certifications. Our metric is built on top of a simple
and intuitive model of trust and risk based on ``utility sampling'', which maybe of interest for non-monetary applications as well.

2005

EPRINT

A Simple and Provably Good Code for SHA Message Expansion
Abstract

We develop a new computer assisted technique for lower bounding the
minimum distance of linear codes similar to those used in SHA-1
message expansion. Using this technique, we prove that a modified
SHA-1 like code has minimum distance at least 82, and that too in
just the last 64 of the 80 expanded words. Further the minimum
weight in the last 60 words (last 48 words) is at least 75 (52
respectively). We propose a new compression function which is
identical to SHA-1 except for the modified message expansion code.
We argue that the high minimum weight of the message expansion code
makes the new compression function resistant to recent differential
attacks.

2005

EPRINT

A Matching Lower Bound on the Minimum Weight of SHA-1 Expansion Code
Abstract

Recently, Wang, Yin, and Yu have used a low weight codeword in the SHA-1 message expansion
to show a better than brute force method to find collisions in SHA-1. The codeword they used
has a (bit) weight of 25 in the last 60 of the 80 expanded words. In this paper we show, using
a computer assisted method, that this is indeed the smallest weight codeword. In particular,
we show that the minimum weight over GF2 of any non-zero codeword
in the SHA-1 (linear) message expansion code, projected on the last 60 words, is at least 25.

2005

EPRINT

PRF Domain Extension Using DAGs
Abstract

We prove a general domain extension theorem for
pseudo-random functions (PRFs).
Given a PRF $F$ from $n$ bits to $n$ bits,
it is well known that
employing $F$ in a chaining mode (CBC-MAC)
yields a PRF on the bigger domain. Viewing each application of $F$
in this chaining mode to be a node in a graph, and the chaining as the edges
between the nodes, the resulting graph is just a line graph.
In this paper, we show that the underlying graph can be an arbitrary
directed acyclic graph (DAG), and
the resulting function on the larger domain is still a PRF.
The only requirement on the graph is that it have unique
source and sink nodes, and no two nodes have the same set of incident nodes.
A new highly parallelizable MAC construction follows
which has a critical path of only $3+\log ^{*} n $ applications of $F$.\\
\hspace*{0.1in}
If we allow Galois field arithmetic, we can consider edge colored DAGs,
where the colors represent multiplication in the field by the color number.
We prove an even more general theorem, where the only restriction on
the colored DAGs is that if two nodes ($u$ and $v$)
have the same set of incident nodes $W$,
then at least one $w$ in $W$ is incident on $u$ and $v$
with a different colored edge.
PMAC (parallelizable message authentication \cite{black})
is a simple example of such graphs. The general thoerem allows one to have
further optimizations over PMAC, and many modes which deal with variable
lengths.

2005

EPRINT

Is SHA-1 conceptually sound?
Abstract

We argue that if the message expansion code of SHA-1 is replaced
by a linear code with a better minimum distance, then the resulting
hash function is collision resistant. To support this argument,
we characterize the disturbance vectors which are used to build
local collision attacks as a linear code. This linear code is the xor-sum of two codes, the message expansion code and a linear code representing the underlying block cipher in SHA-1.
We also show that the following constraint satisfaction problem is
$\np$-hard. The constraints are restricted to being XOR constraints,
or Majority constraints on at most three variables each. The
instances are further restricted by requiring that the constraints
can be listed in a sequence C_1, C_2,...,C_m, such that for
every constraint C_i, two of the variables in it occur only in
constraints C_j, with |j-i|< 48. This problem is similar to the
problem modeling the one-way function property of SHA-1.

2002

EPRINT

Scream: a software-efficient stream cipher
Abstract

We report on the design of Scream, a new software-efficient stream
cipher, which was designed to be a ``more secure SEAL''. Following SEAL, the design of Scream resembles in many ways a block-cipher design. The new cipher is roughly as fast as SEAL, but we believe that it offers a significantly higher security level. In the process of designing this cipher, we re-visit the SEAL design paradigm, exhibiting some tradeoffs and limitations.

2002

EPRINT

Cryptanalysis of stream ciphers with linear masking
Abstract

We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a ``non-linear process'' (say, akin to a round function in block ciphers), and a ``linear process'' such as an LFSR (or even fixed tables). The output of the cipher can be the linear sum of both processes. To attack such ciphers, we look for any property of the ``non-linear process'' that can be distinguished from random. In addition, we look for a linear combination of the linear process that vanishes. We then consider the same linear combination applied to the cipher's output, and try to find traces of the distinguishing property.
In this report we analyze two specific ``distinguishing properties''. One is a linear approximation of the non-linear process, which we demonstrate on the stream cipher SNOW. This attack needs roughly $2^{95}$ words of output, with work-load of about $2^{100}$. The other is a ``low-diffusion'' attack, that we apply to the cipher Scream-0. The latter attack needs only about $2^{43}$ bytes of output, using roughly $2^{50}$ space and $2^{80}$ time.

2002

EPRINT

Tight Lower Bound on Linear Authenticated Encryption
Abstract

We show that any scheme
to encrypt m blocks of size n bits while assuring
message integrity,
that
apart from using m+k invocations of
random functions (from n bits
to n bits) and vn bits of randomness, is linear in (GF2)^n,
must have k+v at least Omega(log m).
This lower bound is proved in a very general model which rules
out many promising linear modes of operations for encryption
with message integrity.
This lower bound is
tight as linear
schemes to encrypt m blocks while
assuring message integrity by using only m+2+log m invocations
are known.
of random permutations.

2002

EPRINT

Parallelizable Authentication Trees
Abstract

We define a new authentication tree in the symmetric key setting,
which has the same computational time, storage
and security parameters as the well
known Merkle authentication tree, but which unlike the latter, allows
for all the cryptographic operations required for an update to be performed
in parallel. The cryptographic operations required for verification can
also be parallelized. In particular, we show a provably secure scheme for
incremental MAC with partial authentication secure against substitution and
replay attacks, which on total data of size $2^n$ blocks,
and given $n$ cryptographic engines,
can compute incremental macs and perform
individual block authentication with
a critical path of only one cryptographic operation

2000

EPRINT

Encryption Modes with Almost Free Message Integrity
Abstract

We define a new mode of operation for block encryption which in
addition to assuring confidentiality also assures message integrity.
In contrast, previously for message integrity a separate pass was
required to compute a cryptographic message authentication code (MAC).
The new mode of operation, called Integrity Aware CBC (IACBC),
requires a total of m + log m block encryptions on a plaintext of
length m blocks. The well known CBC (cipher block chaining) mode
requires m block encryptions. The second pass of computing the MAC
essentially requires additional m block encryptions. We also show a
lower bound of \Omega(log m) additional block encryptions for any
reasonably modeled (linear) scheme which assures message integrity
along with confidentiality.

1998

EPRINT

Secure Distributed Storage and Retrieval
Abstract

In his well-known Information Dispersal Algorithm paper, Rabin showed
a way to distribute information in n pieces among n servers in such a
way that recovery of the information is possible in the presence of up
to t inactive servers. An enhanced mechanism to enable construction
in the presence of malicious faults, which can intentionally modify
their pieces of the information, was later presented by Krawczyk.
Yet, these methods assume that the malicious faults occur only at
reconstruction time. <P>
In this paper we address the more general problem of secure storage
and retrieval of information (SSRI), and guarantee that also the
process of storing the information is correct even when some of the
servers fail. Our protocols achieve this while maintaining the
(asymptotical) space optimality of the above methods. <P>
We also consider SSRI with the added requirement of confidentiality,
by which no party except for the rightful owner of the information is
able to learn anything about it. This is achieved through novel
applications of cryptographic techniques, such as the distributed
generation of receipts, distributed key management via threshold
cryptography, and ``blinding.'' <P>
An interesting byproduct of our scheme is the construction of a secret
sharing scheme with shorter shares size in the amortized sense. An
immediate practical application of our work is a system for the secure
deposit of sensitive data. We also extend SSRI to a ``proactive''
setting, where an adversary may corrupt all the servers during the
lifetime of the system, but only a fraction during any given time
interval.

#### Program Committees

- Eurocrypt 2015
- Eurocrypt 2014
- FSE 2010
- TCC 2009
- FSE 2008
- FSE 2007
- FSE 2006
- FSE 2004
- Crypto 2003

#### Coauthors

- Masayuki Abe (2)
- Dakshi Agrawal (1)
- David Cash (1)
- Suresh Chari (1)
- Don Coppersmith (5)
- Jean-Sébastien Coron (1)
- Pradeep K. Dubey (1)
- Juan A. Garay (1)
- Rosario Gennaro (1)
- Craig Gentry (1)
- François Grieu (1)
- Shai Halevi (8)
- Eric Hall (1)
- William Eric Hall (2)
- Stanislaw Jarecki (1)
- Hugo Krawczyk (1)
- Vijay Kumar (1)
- David Naccache (1)
- Miyako Ohkubo (3)
- Jiaxin Pan (1)
- Anindya C. Patthak (3)
- Tal Rabin (1)
- Josyula R. Rao (2)
- Mariana Raykova (1)
- Pankaj Rohatgi (2)
- Marcel-Catalin Rosu (1)
- Arnay Roy (10)
- Arnab Roy (1)
- Atri Rudra (1)
- Michael Steiner (1)
- Julien P. Stern (1)
- Yuyu Wang (1)