Abstract In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme. While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure. Specifically, our protocol does not fit into thelinear identification protocolabstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT’19), which was used to generically construct Schnorr-like blind signatures based on modules such as classical groups and lattices. Consequently, our scheme is provably secure in the random oracle model (ROM) against poly-logarithmically-many concurrent sessions assuming the subexponential hardness of the group action inverse problem. In more detail, our blind signature exploits thequadratic twistof an elliptic curve in an essential way to endow isogenies with a strictly richer structure than abstract group actions (but still more restrictive than modules). The basic scheme has public key size 128 B and signature size 8 KB under the CSIDH-512 parameter sets—these are the smallest among all provably secure post-quantum secure blind signatures. Relying on a newringvariant of the group action inverse problem ( $$\textsf{rGAIP}$$ rGAIP ), we can halve the signature size to 4 KB while increasing the public key size to 512 B. We provide preliminary cryptanalysis of $${\textsf{rGAIP}} $$ rGAIP and show that for certain parameter settings, it is essentially as secure as the standard $$\textsf{GAIP}$$ GAIP . Finally, we show a novel way to turn our blind signature into a partially blind signature, where we deviate from prior methods since they require hashing into the set of public keys while hiding the corresponding secret key—constructing such a hash function in the isogeny setting remains an open problem.

Abstract We construct an efficient dynamic group signature (or more generally an accountable ring signature) from isogeny and lattice assumptions. Our group signature is based on a simple generic construction that can be instantiated by cryptographically hard group actions such as the CSIDH group action or an MLWE-based group action. The signature is of size $$O(\log N)$$ O ( log N ) , where N is the number of users in the group. Our idea builds on the recent efficient OR-proof by Beullens, Katsumata, and Pintore (Asiacrypt’20), where we efficiently add a proof of valid ciphertext to their OR-proof and further show that the resulting non-interactive zero-knowledge proof system is online extractable . Our group signatures satisfy more ideal security properties compared to previously known constructions, while simultaneously having an attractive signature size. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known post-quantum group signatures (e.g., 6.6 KB for 64 members). In comparison, our lattice-based construction has a larger signature size (e.g., either 126 KB or 89 KB for 64 members depending on the satisfied security property). However, since the $$O(\cdot )$$ O ( · ) -notation hides a very small constant factor, it remains small even for very large group sizes, say $$2^{20}$$ 2 20 .

Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group members), since their knowledge is often needed by the server in order to ensure the proper function of the SGM protocol.

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ü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).

Continuous group key agreements (CGKAs) are a class of protocols that can provide strong security guarantees to secure group messaging protocols such as Signal and MLS. Protection against device compromise is provided by commit messages: at a regular rate, each group member may refresh their key material by uploading a commit message, which is then downloaded and processed by all the other members. In practice, propagating commit messages dominates the bandwidth consumption of existing CGKAs.

Biometric authentication is one of the promising alternatives to standard password-based authentication offering better usability and security. In this work, we revisit the biometric authentication based on fuzzy signatures introduced by Takahashi et al. (ACNS'15, IJIS'19). These are special types of digital signatures where the secret signing key can be a ''fuzzy'' data such as user's biometrics. Compared to other cryptographically secure biometric authentications as those relying on fuzzy extractors, the fuzzy signature-based scheme provides a more attractive security guarantee. However, despite their potential values, fuzzy signatures have not attracted much attention owing to their theory-oriented presentations in all prior works. For instance, the discussion on the practical feasibility of the assumptions (such as the entropy of user biometrics), which the security of fuzzy signatures hinges on, is completely missing.

Abstract Privacy risks of collaborative filtering (CF) have been widely studied. The current state-of-theart inference attack on user behaviors (e.g., ratings/purchases on sensitive items) for CF is by Calandrino et al. (S&P, 2011). They showed that if an adversary obtained a moderate amount of user’s public behavior before some timeT, she can infer user’s private behavioraftertimeT. However, the existence of an attack that infers user’s private behaviorbefore Tremains open. In this paper, we propose the first inference attack that reveals past private user behaviors. Our attack departs from previous techniques and is based onmodel inversion(MI). In particular, we propose the first MI attack on factorization-based CF systems by leveraging data poisoning by Li et al. (NIPS, 2016) in a novel way. We inject malicious users into the CF system so that adversarialy chosen “decoy” items are linked with user’s private behaviors. We also show how to weaken the assumption made by Li et al. on the information available to the adversary from the whole rating matrix to only the item profile and how to create malicious ratings effectively. We validate the effectiveness of our inference algorithm using two real-world datasets.

While online services based on machine learning (ML) have been attracting considerable attention in both academic and business, privacy issues are becoming a threat that cannot be ignored. Recently, Fredrikson et al. [USENIX 2014] proposed a new paradigm of model inversion attacks, which allows an adversary to expose the sensitive information of users by using an ML system for an unintended purpose. In particular, the attack reveals the sensitive attribute values of the target user by using their non-sensitive attributes and the output of the ML model. Here, for the attack to succeed, the adversary needs to possess the non-sensitive attribute values of the target user prior to the attack. However, in reality, even if this information (i.e., non-sensitive attributes) is not necessarily information the user regards as sensitive, it may be difficult for the adversary to actually acquire it. In this paper, we propose a general model inversion (GMI) framework to capture the above scenario where knowledge of the non-sensitive attributes is not necessarily provided. Here, our framework also captures the scenario of Fredrikson et al. Notably, we generalize the paradigm of Fredrikson et al. by additionally modeling the amount of auxiliary information the adversary possesses at the time of the attack. Our proposed GMI framework enables a new type of model inversion attack for prediction systems, which can be carried out without knowledge of the non-sensitive attributes. At a high level, we use the paradigm of data poisoning in a novel way and inject malicious data into the set of training data to modify the ML model into a target ML model, which we can attack without having to have knowledge of the non-sensitive attributes. Our new attack enables the inference of sensitive attributes in the user input from only the output of the ML model, even when the non-sensitive attributes of the user are not available to the adversary. Finally, we provide a concrete algorithm of our model inversion attack on prediction systems based on linear regression models, and give a detailed description of how the data poisoning algorithm is constructed.We evaluate the performance of our new model inversion attack without the knowledge of non-sensitive attributes through experiments with actual data sets.

In this paper we consider robust classifications and show equivalence between the regularized classifications. In general, robust classifications are used to create a classifier robust to data by taking into account the uncertainty of the data. Our result shows that regularized classifications inherit robustness and provide reason on why some regularized classifications tend to be robust against data. Although most robust classification problems assume that every uncertain data lie within an identical bounded set, this paper considers a generalized model where the sizes of the bounded sets are different for each data. These models can be transformed into regularized classification models where the penalties for each data are assigned according to their losses. We see that considering such models opens up for new applications. For an example, we show that this robust classification technique can be used for Imbalanced Data Learning. We conducted experimentation with actual data and compared it with other IDL algorithms such as Cost Sensitive SVMs. This is a novel usage for the robust classification scheme and encourages it to be a suitable candidate for imbalanced data learning.