Books

1. Arbitrary Univariate Function Evaluation and Re-Encryption Protocols over Lifted-ElGamal Type Ciphertexts

著者 :
Koji Nuida, Satsuya Ohata, Shigeo Mitsunari, and Nuttapong Attrapadung

掲載誌 :
Cryptology ePrint Archive: Report 2019/1233, https://eprint.iacr.org/2019/1233

Homomorphic encryption (HE) is one of the main tools in secure multiparty computation (MPC), and the (elliptic-curve) lifted-ElGamal cryptosystem is certainly the most efficient among the existing HE schemes. However, the combination of MPC with this most efficient HE has rarely appeared in the literature. This is mainly because the major known techniques for (additively) HE-based MPC are not available for this scheme due to its typical restriction that only a plaintext in a small range can be efficiently decrypted.

In this paper, we resolve this problem. By our technique, a Server having a lifted-ElGamal ciphertext [[m]][[m]] with unknown small plaintext mm can obtain a ciphertext [[φ(m)]][[φ(m)]] for an arbitrary function φφ by just one-round communication with a semi-honest Client (and also two-rounds with a malicious Client) having a decryption key, where mm is kept secret for both parties. This property enlarges much the variations of MPC based on the most efficient lifted-ElGamal cryptosystem. As an application, we implemented MPC for exact edit distance between two encrypted strings; our experiment for strings of length 10241024 shows that the protocol takes only 4545 seconds in LAN environments and about 33 minutes even in WAN environments. Moreover, our technique is also available with other “lifted-ElGamal type” HE schemes and admits different keys/schemes for the original and the resulting ciphertexts. For example, we can securely convert a level-2 (i.e., after multiplication) ciphertext for some two-level HE schemes into a level-1 (i.e., before multiplication) ciphertext, and securely apply arbitrary functions φ(m)φ(m) to encrypted plaintexts for some attribute-based HE schemes. This is the first result (even by using communication) on realizing these two functionalities.

2. Attribute Based Encryption (and more) for Nondeterministic Finite Automata from LWE

著者 :
Shweta Agrawal, Monosij Maitra, and Shota Yamada

掲載誌 :
Cryptology ePrint Archive: Report 2019/629, https://eprint.iacr.org/2019/629

Constructing Attribute Based Encryption (ABE) [SW05] for uniform models of computation from standard assumptions, is an important problem, about which very little is known. The only known ABE schemes in this setting that i) avoid reliance on multilinear maps or indistinguishability obfuscation, ii) support unbounded length inputs and iii) permit unbounded key requests to the adversary in the security game, are by Waters from Crypto, 2012 [Wat12] and its variants. Waters provided the first ABE for Deterministic Finite Automata (DFA) satisfying the above properties, from a parametrized or “q-type” assumption over bilinear maps. Generalizing this construction to Nondeterministic Finite Automata (NFA) was left as an explicit open problem in the same work, and has seen no progress to date. Constructions from other assumptions such as more standard pairing based assumptions, or lattice based assumptions has also proved elusive.

In this work, we construct the first symmetric key attribute based encryption scheme for nondeterministic finite automata (NFA) from the learning with errors (LWE) assumption. Our scheme supports unbounded length inputs as well as unbounded length machines. In more detail, secret keys in our construction are associated with an NFA M of unbounded length, ciphertexts are associated with a tuple (x;m) where x is a public attribute of unbounded length and m is a secret message bit, and decryption recovers m if and only if M(x) = 1.

Further, we leverage our ABE to achieve (restricted notions of) attribute hiding analogous to the circuit setting, obtaining the first predicate encryption and bounded key functional encryption schemes for NFA from LWE. We achieve machine hiding in the single/bounded key setting to obtain the first reusable garbled NFA from standard assumptions. In terms of lower bounds, we show that secret key functional encryption even for DFAs, with security against unbounded key requests implies indistinguishability obfuscation (iO) for circuits; this suggests a barrier in achieving full fledged functional encryption for NFA.

3. Attribute Based Encryption for Deterministic Finite Automata from DLIN

著者 :
Shweta Agrawal, Monosij Maitra, and Shota Yamada

掲載誌 :
Cryptology ePrint Archive: Report 2019/645, https://eprint.iacr.org/2019/645

Waters [Crypto, 2012] provided the first attribute based encryption scheme ABE for Deterministic Finite Automata (DFA) from a parametrized or “q-type” assumption over bilinear maps. Obtaining a construction from static assumptions has been elusive, despite much progress in the area of ABE.

In this work, we construct the first attribute based encryption scheme for DFA from static assumptions on pairings, namely, the DLIN assumption. Our scheme supports unbounded length inputs, unbounded length machines and unbounded key requests. In more detail, secret keys in our construction are associated with a DFA MM of unbounded length, ciphertexts are associated with a tuple (x,b)(x,b) where xx is a public attribute of unbounded length and bb is a secret message bit, and decryption recovers bb if and only if M(x)=1M(x)=1.

Our techniques are at least as interesting as our final result. We present a simple compiler that combines constructions of unbounded ABE schemes for monotone span programs (MSP) in a black box way to construct ABE for DFA. In more detail, we find a way to embed DFA computation into monotone span programs, which lets us compose existing constructions (modified suitably) of unbounded key-policy ABE (kpABE) and unbounded ciphertext-policy ABE (cpABE) for MSP in a simple and modular way to obtain key-policy ABE for DFA. Our construction uses its building blocks in a symmetric way — by swapping the use of the underlying kpABE and cpABE, we also obtain a construction of ciphertext-policy ABE for DFA.

Our work extends techniques developed recently by Agrawal, Maitra and Yamada [Crypto 2019], which show how to construct ABE that support unbounded machines and unbounded inputs by combining ABE schemes that are bounded in one co-ordinate. At the heart of our work is the observation that unbounded, multi-use ABE for MSP already achieve most of what we need to build ABE for DFA.

4. CCA Security and Trapdoor Functions via Key-Dependent-Message Security

著者 :
Fuyuki Kitagawa, Takahiro Matsuda, and Keisuke Tanaka

掲載誌 :
Cryptology ePrint Archive: Report 2019/291, https://eprint.iacr.org/2019/291

We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, we aim at finding a unified approach and some additional requirement to realize IND-CCA secure PKE and TDF based on IND-CPA secure PKE, and show the following two main results.

As the first main result, we show how to achieve IND-CCA security via a weak form of key-dependent-message (KDM) security. More specifically, we construct an IND-CCA secure PKE scheme based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions (projection-KDM security). Projection functions are very simple functions with respect to which KDM security has been widely studied. Since the existence of projection-KDM secure PKE implies that of the above two building blocks, as a corollary of this result, we see that the existence of IND-CCA secure PKE is implied by that of projection-KDM secure PKE.

As the second main result, we extend the above construction of IND-CCA secure PKE into that of TDF by additionally requiring a mild requirement for each building block. Our TDF satisfies adaptive one-wayness. We can instantiate our TDF based on a wide variety of computational assumptions. Especially, we obtain the first TDF (with adaptive one-wayness) based on the sub-exponential hardness of constant-noise learning-parity-with-noise (LPN) problem.

5. CPA-to-CCA Transformation for KDM Security

著者 :
Fuyuki Kitagawa and Takahiro Matsuda

掲載誌 :
Cryptology ePrint Archive: Report 2019/609, https://eprint.iacr.org/2019/609

We show that chosen plaintext attacks (CPA) security is equivalent to chosen ciphertext attacks (CCA) security for key-dependent message (KDM) security. Concretely, we show how to construct a public-key encryption (PKE) scheme that is KDM-CCA secure with respect to all functions computable by circuits of a-priori bounded size, based only on a PKE scheme that is KDM-CPA secure with respect to projection functions. Our construction works for KDM security in the single user setting.

Our main result is achieved by combining the following two steps. First, we observe that by combining the results and techniques from the recent works by Lombardi et al. (CRYPTO 2019), and by Kitagawa et al. (CRYPTO 2019), we can construct a reusable designated-verifier non-interactive zero-knowledge (DV-NIZK) argument system based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions. This observation leads to the first reusable DV-NIZK argument system under the learning-parity-with-noise (LPN) assumption. Then, as the second and main technical step, we show a generic construction of a KDM-CCA secure PKE scheme using an IND-CPA secure PKE scheme, a reusable DV-NIZK argument system, and an SKE scheme satisfying one-time KDM security with respect to projection functions. Since the classical Naor-Yung paradigm (STOC 1990) with a DV-NIZK argument system does not work for proving KDM security, we propose a new construction methodology to achieve this generic construction.

Moreover, we show how to extend our generic construction and achieve KDM-CCA security in the multi-user setting, by additionally requiring the underlying SKE scheme in our generic construction to satisfy a weak form of KDM security against related-key attacks (RKA-KDM security) instead of one-time KDM security. From this extension, we obtain the first KDM-CCA secure PKE schemes in the multi-user setting under the CDH or LPN assumption.

6. Exploring Constructions of Compact NIZKs from Various Assumptions

著者 :
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa

掲載誌 :
Cryptology ePrint Archive: Report 2019/623, https://eprint.iacr.org/2019/623

A non-interactive zero-knowledge (NIZK) protocol allows a prover to non-interactively convince a verifier of the truth of the statement without leaking any other information. In this study, we explore shorter NIZK proofs for all NP languages. Our primary interest is NIZK proofs from falsifiable pairing/pairing-free group-based assumptions. Thus far, NIZKs in the common reference string model (CRS-NIZKs) for NP based on falsifiable pairing-based assumptions all require a proof size at least as large as O(|C|k)O(|C|k), where CC is a circuit computing the NP relation and kk is the security parameter. This holds true even for the weaker designated-verifier NIZKs (DV-NIZKs). Notably, constructing a (CRS, DV)-NIZK with proof size achieving an additive-overhead O(|C|)+poly(k)O(|C|)+poly(k), rather than a multiplicative-overhead |C|⋅poly(k)|C|⋅poly(k), based on any falsifiable pairing-based assumptions is an open problem.

In this work, we present various techniques for constructing NIZKs with compact proofs, i.e., proofs smaller than O(|C|)+poly(k)O(|C|)+poly(k), and make progress regarding the above situation. Our result is summarized below.

– We construct CRS-NIZK for all NP with proof size |C|+poly(k)|C|+poly(k) from a (non-static) falsifiable Diffie-Hellman (DH) type assumption over pairing groups. This is the first CRS-NIZK to achieve a compact proof without relying on either lattice-based assumptions or non-falsifiable assumptions. Moreover, a variant of our CRS-NIZK satisfies universal composability (UC) in the erasure-free adaptive setting. Although it is limited to NP relations in NC1, the proof size is |w|⋅poly(k)|w|⋅poly(k) where ww is the witness, and in particular, it matches the state-of-the-art UC-NIZK proposed by Cohen, shelat, and Wichs (EPRINT’18) based on lattices. – We construct (multi-theorem) DV-NIZKs for NP with proof size |C|+poly(k)|C|+poly(k) from the computational DH assumption over pairing-free groups. This is the first DV-NIZK that achieves a compact proof from a standard DH type assumption. Moreover, if we further assume the NP relation to be computable in NC1 and assume hardness of a (non-static) falsifiable DH type assumption over pairing-free groups, the proof size can be made as small as |w|+poly(k)|w|+poly(k).

Another related but independent issue is that all (CRS, DV)-NIZKs require the running time of the prover to be at least |C|⋅poly(k)|C|⋅poly(k). Considering that there exists NIZKs with efficient verifiers whose running time is strictly smaller than |C||C|, it is an interesting problem whether we can construct prover-efficient NIZKs. To this end, we construct prover-efficient CRS-NIZKs for NP with compact proof through a generic construction using laconic functional evaluation schemes (Quach, Wee, and Wichs (FOCS’18)). This is the first NIZK in any model where the running time of the prover is strictly smaller than the time it takes to compute the circuit CC computing the NP relation.

Finally, perhaps of an independent interest, we formalize the notion of homomorphic equivocal commitments, which we use as building blocks to obtain the first result, and show how to construct them from pairing-based assumptions.

7. Field Extension in Secret-Shared Form and Its Applications to Efficient Secure Computation

著者 :
Ryo Kikuchi, Nuttapong Attrapadung, Koki Hamada, Dai Ikarashi, Ai Ishida, Takahiro Matsuda, Yusuke Sakai, and Jacob C. N. Schuldt

掲載誌 :
Cryptology ePrint Archive: Report 2019/386, https://eprint.iacr.org/2019/386

Secure computation enables participating parties to jointly compute a function over their inputs while keeping them private. Secret sharing plays an important role for maintaining privacy during the computation. In most schemes, secret sharing over the same finite field is normally utilized throughout all the steps in the secure computation. A major drawback of this “uniform” approach is that one has to set the size of the field to be as large as the maximum of all the lower bounds derived from all the steps in the protocol. This easily leads to a requirement for using a large field which, in turn, makes the protocol inefficient. In this paper, we propose a “non-uniform” approach: dynamically changing the fields so that they are suitable for each step of computation. At the core of our approach is a surprisingly simple method to extend the underlying field of a secret sharing scheme, in a non-interactive manner, while maintaining the secret being shared. Using our approach, default computations can hence be done in a small field, which allows better efficiency, while one would extend to a larger field only at the necessary steps. As the main application of our technique, we show an improvement upon the recent actively secure protocol proposed by Chida et al. (Crypto’18). The improved protocol can handle a binary field, which enables XOR-free computation of a boolean circuit. Other applications include efficient (batch) equality check and consistency check protocols, which are useful for, e.g., password-based threshold authentication

8. Identity-Based Encryption with Security against the KGC: A Formal Model and Its Instantiations

著者 :
Keita Emura, Shuichi Katsumata, and Yohei Watanabe

掲載誌 :
Cryptology ePrint Archive: Report 2019/1384, https://eprint.iacr.org/2019/1384

The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list, and hence it can easily guess the identities corresponding to given ciphertexts. Chow later amended this issue by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, since Chow separately defined the security of IBE and that of the anonymous key-issuing protocol, his IBE definition did not provide any formal treatment when the ICA is used to authenticate the users. Effectively, all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem.

In this paper, based on Chow’s work, we formally define an IBE scheme that resolves the key escrow problem and provide formal definitions of security against corrupted users, KGC, and ICA. Along the way, we observe that if we are allowed to assume a fully trusted ICA, as in Chow’s work, then we can construct a trivial (and meaningless) IBE scheme that is secure against the KGC. Finally, we present two instantiations in our new security model: a lattice-based construction based on the Gentry–Peikert–Vaikuntanathan IBE scheme (STOC 2008) and R{\”{u}}ckert’s lattice-based blind signature scheme (ASIACRYPT 2010), and a pairing-based construction based on the Boneh–Franklin IBE scheme (CRYPTO 2001) and Boldyreva’s blind signature scheme (PKC 2003).

9. Proper Usage of the Group Signature Scheme in ISO/IEC 20008-2

著者 :
Ai Ishida, Yusuke Sakai, Keita Emura, Goichiro Hanaoka, and Keisuke Tanaka

掲載誌 :
Cryptology ePrint Archive: Report 2019/284, https://eprint.iacr.org/2019/284

In ISO/IEC 20008-2, several anonymous digital signature schemes are specified. Among these, the scheme denoted as Mechanism 6, is the only plain group signature scheme that does not aim at providing additional functionalities. The Intel Enhanced Privacy Identification (EPID) scheme, which has many applications in connection with Intel Software Guard Extensions (Intel SGX), is in practice derived from Mechanism 6. In this paper, we firstly show that Mechanism 6 does not satisfy anonymity in the standard security model, i.e., the Bellare-Shi-Zhang model [CT-RSA 2005]. We then provide a detailed analysis of the security properties offered by Mechanism 6 and characterize the conditions under which its anonymity is preserved. Consequently, it is seen that Mechanism 6 is secure under the condition that the issuer, who generates user signing keys, does not join the attack. We also derive a simple patch for Mechanism 6 from the analysis.

10. Simple and Efficient KDM-CCA Secure Public Key Encryption

著者 :
Fuyuki Kitagawa, Takahiro Matsuda, and Keisuke Tanaka

掲載誌 :
Cryptology ePrint Archive: Report 2019/1012, https://eprint.iacr.org/2019/1012

We propose two efficient public key encryption (PKE) schemes satisfying key dependent message security against chosen ciphertext attacks (KDM-CCA security). The first one is KDM-CCA secure with respect to affine functions. The other one is KDM-CCA secure with respect to polynomial functions. Both of our schemes are based on the KDM-CPA secure PKE schemes proposed by Malkin, Teranishi, and Yung (EUROCRYPT 2011). Although our schemes satisfy KDM-CCA security, their efficiency overheads compared to Malkin et al.’s schemes are very small. Thus, efficiency of our schemes is drastically improved compared to the existing KDM-CCA secure schemes.

We achieve our results by extending the construction technique by Kitagawa and Tanaka (ASIACRYPT 2018). Our schemes are obtained via semi-generic constructions using an IND-CCA secure PKE scheme as a building block. We prove the KDM-CCA security of our schemes based on the decisional composite residuosity (DCR) assumption and the IND-CCA security of the building block PKE scheme.

Moreover, our security proofs are tight if the IND-CCA security of the building block PKE scheme is tightly reduced to its underlying computational assumption. By instantiating our schemes using existing tightly IND-CCA secure PKE schemes, we obtain the first tightly KDM-CCA secure PKE schemes whose ciphertext consists only of a constant number of group elements.

11. Compact NIZKs from Standard Assumptions on Bilinear Maps

著者 :
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa

掲載誌 :
Cryptology ePrint Archive: Report 2020/223, https://eprint.iacr.org/2020/223

A non-interactive zero-knowledge (NIZK) protocol enables a prover to convince a verifier of the truth of a statement without leaking any other information by sending a single message. The main focus of this work is on exploring short pairing-based NIZKs for all NP languages based on standard assumptions. In this regime, the seminal work of Groth, Ostrovsky, and Sahai (J.ACM’12) (GOS-NIZK) is still considered to be the state-of-the-art. Although fairly efficient, one drawback of GOS-NIZK is that the proof size is multiplicative in the circuit size computing the NP relation. That is, the proof size grows by O(|C|λ)O(|C|λ), where CC is the circuit for the NP relation and λλ is the security parameter. By now, there have been numerous follow-up works focusing on shortening the proof size of pairing-based NIZKs, however, thus far, all works come at the cost of relying either on a non-standard knowledge-type assumption or a non-static qq-type assumption. Specifically, improving the proof size of the original GOS-NIZK under the same standard assumption has remained as an open problem.

Our main result is a construction of a pairing-based NIZK for all of NP whose proof size is additive in |C||C|, that is, the proof size only grows by |C|+\poly(λ)|C|+\poly(λ), based on the decisional linear (DLIN) assumption. Since the DLIN assumption is the same assumption underlying GOS-NIZK, our NIZK is a strict improvement on their proof size.

As by-products of our main result, we also obtain the following two results: (1) We construct a perfectly zero-knowledge NIZK (NIPZK) for NP relations computable in NC1 with proof size |w|⋅\poly(λ)|w|⋅\poly(λ) where |w||w| is the witness length based on the DLIN assumption. This is the first pairing-based NIPZK for a non-trivial class of NP languages whose proof size is independent of |C||C| based on a standard assumption. (2)~We construct a universally composable (UC) NIZK for NP relations computable in NC1 in the erasure-free adaptive setting whose proof size is |w|⋅\poly(λ)|w|⋅\poly(λ) from the DLIN assumption. This is an improvement over the recent result of Katsumata, Nishimaki, Yamada, and Yamakawa (CRYPTO’19), which gave a similar result based on a non-static qq-type assumption.

The main building block for all of our NIZKs is a constrained signature scheme with decomposable online-offline efficiency. This is a property which we newly introduce in this paper and construct from the DLIN assumption. We believe this construction is of an independent interest.

12. Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512

著者 :
Ali El Kaafarani, Shuichi Katsumata, and Federico Pintore

掲載誌 :
Cryptology ePrint Archive: Report 2020/124, https://eprint.iacr.org/2020/124

Recently, Beullens, Kleinjung, and Vercauteren (Asiacrypt’19) provided the first practical isogeny-based digital signature, obtained from the Fiat-Shamir (FS) paradigm. They worked with the CSIDH-512 parameters and passed through a new record class group computation. However, as with all standard FS signatures, the security proof is highly non-tight and the concrete parameters are set under the heuristic that the only way to attack the scheme is by finding collisions for a hash function. In this paper, we propose an FS-style signature scheme, called Lossy CSI-FiSh, constructed using the CSIDH-512 parameters and with a security proof based on the “Lossy Keys” technique introduced by Kiltz, Lyubashevsky and Schaffner (Eurocrypt’18). Lossy CSI-FiSh is provably secure under the same assumption which underlies the security of the key exchange protocol CSIDH (Castryck et al. (Asiacrypt’18)) and is almost as efficient as CSI-FiSh. For instance, aiming for small signature size, our scheme is expected to take around ≈800≈800ms to sign/verify while producing signatures of size ≈280≈280 bytes. This is only twice slower than CSI-FiSh while having similar signature size for the same parameter set. As an additional benefit, our scheme is by construction secure both in the classical and quantum random oracle model.

13. Optimal Broadcast Encryption from Pairings and LWE

著者 :
Shweta Agrawal and Shota Yamada

掲載誌 :
Cryptology ePrint Archive: Report 2020/228, https://eprint.iacr.org/2020/228

Boneh, Waters and Zhandry (CRYPTO 2014) used multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption (BE) where all parameters in the system are small. In this work, we improve their result by providing a solution that uses only bilinear maps and Learning With Errors (LWE). Our scheme is fully collusion-resistant against any number of colluders, and can be generalized to an identity-based broadcast system with short parameters. Thus, we reclaim the problem of optimal broadcast encryption from the land of “Obfustopia”.

Our main technical contribution is a ciphertext policy attribute based encryption (CP-ABE) scheme which achieves special efficiency properties – its ciphertext size, secret key size, and public key size are all independent of the size of the circuits supported by the scheme. We show that this special CP-ABE scheme implies BE with optimal parameters; but it may also be of independent interest. Our constructions rely on a novel interplay of bilinear maps and LWE, and are proven secure in the generic group model.

14. Unbounded Dynamic Predicate Compositions in ABE from Standard Assumptions

著者 :
Junichi Tomida and Nuttapong Attrapadung

掲載誌 :
Cryptology ePrint Archive: Report 2020/231, https://eprint.iacr.org/2020/231

At Eurocrypt’19, Attrapadung presented several transformations that dynamically compose a set of attribute-based encryption (ABE) schemes for simpler predicates into a new ABE scheme for more expressive predicates. Due to the powerful unbounded and modular nature of his compositions, many new ABE schemes can be obtained in a systematic manner. However, his approach heavily relies on qq-type assumptions, which are not standard. Devising such powerful compositions from standard assumptions was left as an important open problem. In this paper, we present a new framework for constructing ABE schemes that allow unbounded and dynamic predicate compositions among them, and show that the adaptive security of these composed ABE will be preserved by relying only on the standard matrix Diffie-Hellman (MDDH) assumption. This thus resolves the open problem posed by Attrapadung.

As for applications, we obtain various ABEs that are the first such instantiations of their kinds from standard assumptions.These include the following adaptively secure large-universe ABEs for Boolean formulae under MDDH:

– The first completely unbounded monotone key-policy (KP)/ciphertext-policy (CP) ABE. Such ABE was recently proposed, but only for the KP and small-universe flavor (Kowalczyk and Wee, Eurocrypt’19).

– The first completely unbounded non-monotone KP/CP-ABE. Especially, our ABEs support a new type of non-monotonicity that subsumes previous two types of non-monotonicity, namely, by Ostrovsky et al. (CCS’07) and by Okamoto and Takashima (CRYPTO’10).

– The first (non-monotone) KP and CP-ABE with constant-size ciphertexts and secret keys, respectively.

– The first KP and CP-ABE with constant-size secret keys and ciphertexts, respectively.

At the core of our framework lies a new partially symmetric design of the core 1-key 1-ciphertext oracle component called Key Encoding Indistinguishability, which exploits the symmetry so as to obtain compositions.

15. Non-Interactive Zero-Knowledge in Pairing-Free Groups from Weaker Assumptions

著者 :
Geoffroy Couteau, Shuichi Katsumata, and Bogdan Ursu

掲載誌 :
Cryptology ePrint Archive: Report 2020/535, https://eprint.iacr.org/2020/535

We provide two new constructions of non-interactive zero-knowledge arguments (NIZKs) for NP from discrete-logarithm-style assumptions over cyclic groups, without relying on pairings. A previous construction from (Canetti et al., Eurocrypt’18) achieves such NIZKs under the assumption that no efficient adversary can break the key-dependent message (KDM) security of (additive) ElGamal with respect to all (even inefficient) functions over groups of size 2λ2λ, with probability better than poly(λ)/2λpoly(λ)/2λ. This is an extremely strong, non-falsifiable assumption. In particular, even mild (polynomial) improvements over the current best-known attacks on the discrete logarithm problem would already contradict this assumption. (Canetti et al. STOC’19) describe how to improve the assumption to rely only on KDM security with respect to efficient functions while additionally assuming public-key encryption schemes, therefore obtaining an assumption that is (in spirit) falsifiable.

Our first construction improves this state of affairs. We provide a construction of NIZKs for NP under the CDH assumption together with the assumption that no efficient adversary can break the key-dependent message one-wayness of ElGamal with respect to efficient functions over groups of size 2λ2λ, with probability better than poly(λ)/2cλpoly(λ)/2cλ (denoted 2−cλ2−cλ-OWKDM), for a constant c=3/4c=3/4. Unlike the previous assumption, our assumption leaves an exponential gap between the best-known attack and the required security guarantee.

Our second construction is interested in the case where CDH does not hold. Namely, as a second contribution, we construct an infinitely often NIZK argument system for NP (where soundness and zero-knowledge are only guaranteed to hold for infinitely many security parameters), under the assumption that CDH is easy together with the 2−cλ2−cλ-OWKDM security of ElGamal with c=28/29+o(1)c=28/29+o(1) and the existence of low-depth pseudorandom generators (PRG).

Combining our two results, we obtain a construction of (infinitely-often) NIZKs for NP under the 2−cλ2−cλ-OWKDM security of ElGamal with c=28/29+o(1)c=28/29+o(1) and the existence of low-depth PRG, independently of whether CDH holds. To our knowledge, since neither OWKDM security of ElGamal nor low-depth PRGs are known to imply public key encryption, this provides the first construction of NIZKs from concrete and falsifiable Minicrypt-style assumptions.

16. Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices

著者 :
Ward Beullens, Shuichi Katsumata, and Federico Pintore

掲載誌 :
Cryptology ePrint Archive: Report 2020/646, https://eprint.iacr.org/2020/646

We construct efficient ring signatures from isogeny and lattice assumptions. Our ring signatures are based on a logarithmic OR proof for group actions. We then instantiate this group action by either the CSIDH group action or an MLWE-based group action to obtain our isogeny-based or lattice-based ring signature scheme respectively. Even though this OR proof has a binary challenge space and therefore needs to be repeated a linear number of times, the size of our ring signatures is small and scales better with the ring size N than previously known post-quantum ring signatures. We also construct linkable ring signatures that are almost as efficient as the non-linkable variant. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known logarithmic post-quantum ring signatures, but is relatively slow (e.g. 5.5 KB signatures and 79 s signing time for rings with 8 members). In comparison, our lattice-based construction is much faster, but has larger signatures (e.g. 30 KB signatures and 90 ms signing time for the same ring size). For small ring sizes our lattice-based ring signatures are slightly larger than state-of-the-art schemes, but they are smaller for ring sizes larger than N≈1024N≈1024.

17. Efficient Final Exponentiation via Cyclotomic Structure for Pairings over Families of Elliptic Curves

著者 :
Daiki Hayashida, Kenichiro Hayasaka, and Tadanori Teruya

掲載誌 :
Cryptology ePrint Archive: Report 2020/875, https://eprint.iacr.org/2020/875

The final exponentiation, which is the exponentiation by a fixed large exponent, must be performed in the Tate and (optimal) Ate pairing computation to ensure output uniqueness, algorithmic correctness, and security for pairing-based cryptography. In this paper, we propose a new framework of efficient final exponentiation for pairings over families of elliptic curves. Our framework provides two methods: the first method supports families of elliptic curves with arbitrary embedding degrees, and the second method supports families with specific embedding degrees of providing even faster algorithms. Applying our framework to several Barreto-Lynn-Scott families, we obtain faster final exponentiation than the previous state-of-the-art constructions.

18. Circular Security Is Complete for KDM Security

著者 :
Fuyuki Kitagawa and Takahiro Matsuda

掲載誌 :
Cryptology ePrint Archive: Report 2020/1060, https://eprint.iacr.org/2020/1060

Circular security is the most elementary form of key-dependent message (KDM) security, which allows us to securely encrypt only a copy of secret key bits. In this work, we show that circular security is complete for KDM security in the sense that an encryption scheme satisfying this security notion can be transformed into one satisfying KDM security with respect to all functions computable by a-priori bounded-size circuits (bounded-KDM security). This result holds in the presence of any number of keys and in any of secret-key/public-key and CPA/CCA settings. Such a completeness result was previously shown by Applebaum (EUROCRYPT 2011) for KDM security with respect to projection functions (projection-KDM security) that allows us to securely encrypt both a copy and a negation of secret key bits.

Besides amplifying the strength of KDM security, our transformation in fact can start from an encryption scheme satisfying circular security against CPA attacks and results in one satisfying bounded-KDM security against CCA attacks. This result improves the recent result by Kitagawa and Matsuda (TCC 2019) showing a CPA-to-CCA transformation for KDM secure public-key encryption schemes.

19. Scalable Ciphertext Compression Techniques for Post-Quantum KEMs and their Applications

著者 :
Shuichi Katsumata, Kris Kwiatkowski, Federico Pintore, and Thomas Prest

掲載誌 :
Cryptology ePrint Archive: Report 2020/1107, https://eprint.iacr.org/2020/1107

A multi-recipientmulti-recipient key encapsulation mechanism, or mKEMmKEM, provides a scalable solution to securely communicating to a large group, and offers savings in both bandwidth and computational cost compared to the trivial solution of communicating with each member individually. All prior works on mKEMmKEM are only limited to classical assumptions and, although some generic constructions are known, they all require specific properties that are not shared by most post-quantum schemes. In this work, we first provide a simple and efficient generic construction of mKEMmKEM that can be instantiated from versatile assumptions, including post-quantum ones. We then study these mKEMmKEM instantiations at a practical level using 8 post-quantum mKEMmKEMs (which are lattice and isogeny-based NIST candidates), and CSIDH, and show that compared to the trivial solution, our mKEMmKEM offers savings of at least one order of magnitude in the bandwidth, and make encryption time shorter by a factor ranging from 1.92 to 35. Additionally, we show that by combining mKEMmKEM with the TreeKEM protocol used by MLS −− an IETF draft for secure group messaging −− we obtain significant bandwidth savings.

20. Adaptively Secure Inner Product Encryption from LWE

著者 :
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa

掲載誌 :
Cryptology ePrint Archive: Report 2020/1135, https://eprint.iacr.org/2020/1135

Attribute-based encryption (ABE) is an advanced form of encryption scheme allowing for access policies to be embedded within the secret keys and ciphertexts. By now, we have ABEs supporting numerous types of policies based on hardness assumptions over bilinear maps and lattices. However, one of the distinguishing differences between ABEs based on these two breeds of assumptions is that the former can achieve adaptive security for quite expressible policies (e.g., inner-products, boolean formula) while the latter can not. Recently, two adaptively secure lattice-based ABEs have appeared and changed the state of affairs: a non-zero inner-product (NIPE) encryption by Katsumata and Yamada (PKC’19) and an ABE for tt-CNF policies by Tsabary (CRYPTO’19). However, the policies supported by these ABEs are still quite limited and do not embrace the more interesting policies that have been studied in the literature. Notably, constructing an adaptively secure inner-product encryption (IPE) based on lattices still remains open.

In this work, we propose the first adaptively secure IPE based on the learning with errors (LWE) assumption with sub-exponential modulus size (without resorting to complexity leveraging). Concretely, our IPE supports inner-products over the integers ZZ with polynomial sized entries and satisfies adaptively weakly-attribute-hiding security. We also show how to convert such an IPE to an IPE supporting inner-products over ZpZp for a polynomial-sized pp and a fuzzy identity-based encryption (FIBE) for small and large universes. Our result builds on the ideas presented in Tsabary (CRYPTO’19), which uses constrained pseudorandom functions (CPRF) in a semi-generic way to achieve adaptively secure ABEs, and the recent lattice-based adaptively secure CPRF for inner-products by Davidson et al. (CRYPTO’20). Our main observation is realizing how to weaken the conforming CPRF property introduced in Tsabary (CRYPTO’19) by taking advantage of the specific linearity property enjoyed by the lattice evaluation algorithms by Boneh et al. (EUROCRYPT’14).

21. Optimal Broadcast Encryption from LWE and Pairings in the Standard Model

著者 :
Shweta Agrawal, Daniel Wichs, and Shota Yamada

掲載誌 :
Cryptology ePrint Archive: Report 2020/1179, https://eprint.iacr.org/2020/1179

Broadcast Encryption with optimal parameters was a long-standing problem, whose first solution was provided in an elegant work by Boneh, Waters and Zhandry [BWZ14]. However, this work relied on multilinear maps of logarithmic degree, which is not considered a standard assumption. Recently, Agrawal and Yamada [AY20] improved this state of affairs by providing the first construction of optimal broadcast encryption from Bilinear Maps and Learning With Errors (LWE). However, their proof of security was in the generic bilinear group model. In this work, we improve upon their result by providing a new construction and proof in the standard model. In more detail, we rely on the Learning With Errors (LWE) assumption and the Knowledge of OrthogonALity Assumption (KOALA) [BW19] on bilinear groups.

Our construction combines three building blocks: a (computational) nearly linear secret sharing scheme with compact shares which we construct from LWE, an inner-product functional encryption scheme with special properties which is constructed from the bilinear Matrix Decision Diffie Hellman (MDDH) assumption, and a certain form of hyperplane obfuscation, which is constructed using the KOALA assumption. While similar to that of Agrawal and Yamada, our construction provides a new understanding of how to decompose the construction into simpler, modular building blocks with concrete and easy-to-understand security requirements for each one. We believe this sheds new light on the requirements for optimal broadcast encryption, which may lead to new constructions in the future.

22. Recent Advances in Practical Secure Multi-Party Computation

著者 :
Satsuya Ohata

掲載誌 :
IEICE TRANSACTIONS on Fundamentals, vol. E103-A, no. 10, pp.1134-1141, 2020

Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. MPC has been actively studied, and there are many research results both in the theoretical and practical research fields. In this paper, we introduce the basic matters on MPC and show recent practical advances. We first explain the settings, security notions, and cryptographic building blocks of MPC. Then, we show and discuss current situations on higher-level secure protocols, privacy-preserving data analysis, and frameworks/compilers for implementing MPC applications with low-cost.

23. CP-ABE for Circuits (and more) in the Symmetric Key Setting

著者 :
Shweta Agrawal and Shota Yamada

掲載誌 :
Cryptology ePrint Archive: Report 2020/1432, https://eprint.iacr.org/2020/1432

The celebrated work of Gorbunov, Vaikuntanathan and Wee provided the first key policy attribute based encryption scheme (ABE) for circuits from the Learning With Errors (LWE) assumption. However, the arguably more natural ciphertext policy variant has remained elusive, and is a central primitive not yet known from LWE.

In this work, we construct the first symmetric key ciphertext policy attribute based encryption scheme (CP-ABE) for all polynomial sized circuits from the learning with errors (LWE) assumption. In more detail, the ciphertext for a message mm is labelled with an access control policy ff, secret keys are labelled with public attributes xx from the domain of ff and decryption succeeds to yield the hidden message mm if and only if f(x)=1f(x)=1. The size of our public and secret key do not depend on the size of the circuits supported by the scheme — this enables our construction to support circuits of unbounded size (but bounded depth). Our construction is secure against collusions of unbounded size. We note that current best CP-ABE schemes [BSW07,Wat11,LOSTW10,OT10,LW12,RW13,Att14,Wee14,AHY15,CGW15,AC17,KW19] rely on pairings and only support circuits in the class NC1 (albeit in the public key setting).

We adapt our construction to the public key setting for the case of bounded size circuits. The size of the ciphertext and secret key as well as running time of encryption, key generation and decryption satisfy the efficiency properties desired from CP-ABE, assuming that all algorithms have RAM access to the public key. However, the running time of the setup algorithm and size of the public key depends on the circuit size bound, restricting the construction to support circuits of a-priori bounded size. We remark that the inefficiency of setup is somewhat mitigated by the fact that setup must only be run once.

We generalize our construction to consider attribute and function hiding. The compiler of lockable obfuscation upgrades any attribute based encryption scheme to predicate encryption, i.e. with attribute hiding [GKW17,WZ17]. Since lockable obfuscation can be constructed from LWE, we achieve ciphertext policy predicate encryption immediately. For function privacy, we show that the most natural notion of function hiding ABE for circuits, even in the symmetric key setting, is sufficient to imply indistinguishability obfuscation. We define a suitable weakening of function hiding to sidestep the implication and provide a construction to achieve this notion for both the key policy and ciphertext policy case. Previously, the largest function class for which function private predicate encryption (supporting unbounded keys) could be achieved was inner product zero testing, by Shen, Shi and Waters [SSW09].

24. Round-Optimal Blind Signatures in the Plain Model from Classical and Quantum Standard Assumptions

著者 :
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa

掲載誌 :
Cryptology ePrint Archive: Report 2021/306, https://eprint.iacr.org/2021/306

Blind signatures, introduced by Chaum (Crypto’82), allows a user to obtain a signature on a message without revealing the message itself to the signer. Thus far, all existing constructions of round-optimal blind signatures are known to require one of the following: a trusted setup, an interactive assumption, or complexity leveraging. This state-of-the-affair is somewhat justified by the few known impossibility results on constructions of round-optimal blind signatures in the plain model (i.e., without trusted setup) from standard assumptions. However, since all of these impossibility results only hold under some conditions, fully (dis)proving the existence of such round-optimal blind signatures has remained open.

In this work, we provide an affirmative answer to this problem and construct the first round-optimal blind signature scheme in the plain model from standard polynomial-time assumptions. Our construction is based on various standard cryptographic primitives and also on new primitives that we introduce in this work, all of which are instantiable from classical and post-quantum standard polynomial-time assumptions. The main building block of our scheme is a new primitive called a blind-signature-conforming zero-knowledge (ZK) argument system. The distinguishing feature is that the ZK property holds by using a quantum polynomial-time simulator against non-uniform classical polynomial-time adversaries. Syntactically one can view this as a delayed-input three-move ZK argument with a reusable first message, and we believe it would be of independent interest.

25. Chosen Ciphertext Secure Keyed Two-Level Homomorphic Encryption

著者 :
Yusaku Maeda, Koji Nuida

掲載誌 :
Cryptology ePrint Archive: Report 2021/722,https://eprint.iacr.org/2021/722

Homomorphic encryption (HE) is a useful variant of public key encryption (PKE), but it has a drawback that HE cannot fully achieve IND-CCA2 security, which is a standard security notion for PKE. Beyond existing HE schemes achieving weaker IND-CCA1 security, Emura et al.\ (PKC 2013) proposed the notion of \lq\lq keyed\rq\rq{} version of HE, called KH-PKE, which introduces an evaluation key controlling the functionality of homomorphic operations and achieves security stronger than IND-CCA1 and as close to IND-CCA2 as possible. After Emura et al.’s scheme which can evaluate linear polynomials only, Lai et al.\ (PKC 2016) proposed a fully homomorphic KH-PKE, but it requires indistinguishability obfuscation and hence has a drawback in practical feasibility. In this paper, we propose a \lq\lq two-level\rq\rq{} KH-PKE scheme for evaluating degree-two polynomials, by cleverly combining Emura et al.’s generic framework with a recent efficient two-level HE by Attrapadung et al.\ (ASIACCS 2018). Our scheme is the first KH-PKE that can handle non-linear polynomials while keeping practical efficiency.

26. An Efficient and Generic Construction for Signal’s Handshake (X3DH): Post-Quantum, State Leakage Secure, and Deniable

著者 :
Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, and Thomas Prest

掲載誌 :
Cryptology ePrint Archive: Report 2021/616, https://eprint.iacr.org/2021/616

The Signal protocol is a secure instant messaging protocol that underlies the security of numerous applications such as WhatsApp, Skype, Facebook Messenger among many others. The Signal protocol consists of two sub-protocols known as the X3DH protocol and the double ratchet protocol, where the latter has recently gained much attention. For instance, Alwen, Coretti, and Dodis~(Eurocrypt’19) provided a concrete security model along with a generic construction based on simple building blocks that are instantiable from versatile assumptions, including post-quantum ones. In contrast, as far as we are aware, works focusing on the X3DH protocol seem limited.

In this work, we cast the X3DH protocol as a specific type of authenticated key exchange (AKE) protocol, which we call a Signal-conforming AKE protocol, and formally define its security model based on the vast prior work on AKE protocols. We then provide the first efficient generic construction of a Signal-conforming AKE protocol based on standard cryptographic primitives such as key encapsulation mechanisms (KEM) and signature schemes. Specifically, this results in the first post-quantum secure replacement of the X3DH protocol on well-established assumptions. Similar to the X3DH protocol, our Signal-conforming AKE protocol offers a strong (or stronger) flavor of security, where the exchanged key remains secure even when all the non-trivial combinations of the long-term secrets and session-specific secrets are compromised. Moreover, our protocol has a weak flavor of deniability and we further show how to strengthen it using ring signatures. Finally, we provide a full-fledged, generic C implementation of our (weakly deniable) protocol. We instantiate it with several Round 3 candidates (finalists and alternates) to the NIST post-quantum standardization process and compare the resulting bandwidth and computation performances. Our implementation is publicly available.

27. A New Simple Technique to Bootstrap Various Lattice Zero-Knowledge Proofs to QROM Secure NIZKs

著者 :
Shuichi Katsumata

掲載誌 :
Cryptology ePrint Archive: Report 2021/927, https://eprint.iacr.org/2021/927

Many of the recent advanced lattice-based ΣΣ-/public-coin honest verifier (HVZK) interactive protocols based on the techniques developed by Lyubashevsky (Asiacrypt’09, Eurocrypt’12) can be transformed into a non-interactive zero-knowledge (NIZK) proof in the random oracle model (ROM) using the Fiat-Shamir transform. Unfortunately, although they are known to be secure in the classicalclassical ROM, existing proof techniques are incapable of proving them secure in the quantumquantum ROM (QROM). Alternatively, while we could instead rely on the Unruh transform (Eurocrypt’15), the resulting QROM secure NIZK will incur a large overhead compared to the underlying interactive protocol.

In this paper, we present a new simple semi-generic transform that compiles many existing lattice-based ΣΣ-/public-coin HVZK interactive protocols into QROM secure NIZKs. Our transform builds on a new primitive called extractable linear homomorphic commitmentextractable linear homomorphic commitment protocol. The resulting NIZK has several appealing features: it is not only a proof of knowledge but also straight-line extractable; the proof overhead is smaller compared to the Unruh transform; it enjoys a relatively small reduction loss; and it requires minimal background on quantum computation. To illustrate the generality of our technique, we show how to transform the recent Bootle et al.’s 5-round protocol with an exact sound proof (Crypto’19) into a QROM secure NIZK by increasing the proof size by a factor of 2.62.6. This compares favorably to the Unruh transform that requires a factor of more than 5050.