Path: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: IACR ePrint Archive <noreply@example.invalid>
Newsgroups: sci.crypt
Subject: [digest] 2024 Week 43
Date: Mon, 28 Oct 2024 02:31:46 -0000
Organization: A noiseless patient Spider
Lines: 1096
Message-ID: <j3PDRgMT-p1xRpwxERJQxEqBujDgiC4j@eprint.iacr.org.invalid>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 28 Oct 2024 03:31:51 +0100 (CET)
Injection-Info: dont-email.me; posting-host="355ccff351772dc0d243827af986a537";
	logging-data="745616"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+oU1wfXeOfJskcvN5/7L69I/Z1tAN5Sgs="
Cancel-Lock: sha1:QRIjkAI7RdmQefNfIP2iAj3Fxg0=
Bytes: 59362

## In this issue

1. [2024/761] Lattice-based Broadcast Authenticated Searchable ...
2. [2024/763] Incorporating SIS Problem into Luby-Rackoff Cipher
3. [2024/775] Spec-o-Scope: Cache Probing at Cache Speed
4. [2024/1575] Efficiently-Thresholdizable Batched Identity Based ...
5. [2024/1718] Drifting Towards Better Error Probabilities in ...
6. [2024/1719] Compact Pseudorandom Functional Encryption from ...
7. [2024/1720] Pseudorandom Multi-Input Functional Encryption and ...
8. [2024/1721] An Efficient Noncommutative NTRU from Semidirect ...
9. [2024/1722] Revisiting Fermat's Factorization Method
10. [2024/1723] Proving the Security of the Extended Summation- ...
11. [2024/1724] Straight-Line Knowledge Extraction for Multi-Round ...
12. [2024/1725] PISA: Privacy-Preserving Smart Parking
13. [2024/1726] Certified Randomness implies Secure Classical ...
14. [2024/1727] (Quantum) Indifferentiability and Pre-Computation
15. [2024/1728] On Key Substitution Attacks against Aggregate ...
16. [2024/1729] cuTraNTT: A Novel Transposed Number Theoretic ...
17. [2024/1730] Secure and Efficient Outsourced Matrix ...
18. [2024/1731] Arc: Accumulation for Reed--Solomon Codes
19. [2024/1732] Radical 2-isogenies and cryptographic hash ...
20. [2024/1733] One Time Pad and the Short Key Dream
21. [2024/1734] Optimizing Message Range and Ciphertext Storage in ...
22. [2024/1735] The Mysteries of LRA: Roots and Progresses in Side- ...
23. [2024/1736] A graph-theoretic approach to analyzing decoding ...
24. [2024/1737] Embedded Curves and Embedded Families for SNARK- ...
25. [2024/1738] More Efficient Isogeny Proofs of Knowledge via ...
26. [2024/1739] Provably Robust Watermarks for Open-Source Language ...
27. [2024/1740] OpenNTT: An Automated Toolchain for Compiling High- ...
28. [2024/1741] The Learning Stabilizers with Noise problem
29. [2024/1742] Pseudorandom Obfuscation and Applications
30. [2024/1743] The Window Heuristic: Automating Differential Trail ...
31. [2024/1744] PEARL-SCALLOP: Parameter Extension Applicable in ...
32. [2024/1745] Pseudorandomness in the (Inverseless) Haar Random ...

## 2024/761

* Title: Lattice-based Broadcast Authenticated Searchable Encryption for Clou=
d Storage
* Authors: Yibo Cao, Shiyuan Xu, Xiu-Bo Chen, Gang Xu, Siu-Ming Yiu, Zongpeng=
 Li
* [Permalink](https://eprint.iacr.org/2024/761)
* [Download](https://eprint.iacr.org/2024/761.pdf)

### Abstract

For security issue, data in cloud is encrypted. Searching encrypted data (wit=
hout decryption) is a practical and important problem. Public key authenticat=
ed encryption with keyword search (PAEKS) enables the retrieval of encrypted =
data, while resisting the insider keyword guessing attacks (IKGAs). Most PAEK=
S schemes only work with single-receiver model, exhibiting very limited appli=
cability. To address this concern, there have been researches on broadcast au=
thenticated encryption with keyword search (BAEKS) to achieve multi-receiver =
ciphertext search. But to our best knowledge, existing BAEKS schemes are not =
quantum resistant. In this paper, we propose lattice-based BAEKS, the first p=
ost-quantum broadcast authenticated encryption with keyword search in multi-r=
eceiver model. In particular, we leverage several lattice sampling algorithms=
 and rejection sampling technique to construct our BAEKS scheme. We also inco=
rporate the minimal cover set technique and lattice basis extension algorithm=
 to construct an enhanced version, namely FS-BAEKS, which addresses the secre=
t key leakage problem. We give a rigorous security analysis of our schemes. F=
or the efficiency of BAEKS and Test algorithms in our BAEKS scheme, the compu=
tational overheads are at least 2x and 89x faster than the state-of-the-art s=
chemes respectively, which is practical for cloud storage systems.



## 2024/763

* Title: Incorporating SIS Problem into Luby-Rackoff Cipher
* Authors: Yu Morishima, Masahiro Kaminaga
* [Permalink](https://eprint.iacr.org/2024/763)
* [Download](https://eprint.iacr.org/2024/763.pdf)

### Abstract

With the rise of quantum computing, the security of traditional cryptographic=
 systems, especially those vulnerable to quantum attacks, is under threat. Wh=
ile public key cryptography has been widely studied in post-quantum security,=
 symmetric-key cryptography has received less attention. This paper explores =
using the Ajtai-Micciancio hash function, based on the Short Integer Solution=
 (SIS) problem, as a pseudorandom function in the Luby-Rackoff cipher. Since =
lattice-based problems like SIS are believed to resist quantum algorithms, th=
is approach provides the potential for a quantum-resistant block cipher. We a=
lso propose a novel statistical method based on the Generalized Extreme Value=
 distribution to evaluate the number of secure rounds and resistance to diffe=
rential cryptanalysis.



## 2024/775

* Title: Spec-o-Scope: Cache Probing at Cache Speed
* Authors: Gal Horowitz, Eyal Ronen, Yuval Yarom
* [Permalink](https://eprint.iacr.org/2024/775)
* [Download](https://eprint.iacr.org/2024/775.pdf)

### Abstract

Over the last two decades, microarchitectural side channels have been the foc=
us of a large body of research on the development of new attack techniques, e=
xploiting them to attack various classes of targets and designing mitigations=
.. One line of work focuses on increasing the speed of the attacks, achieving =
higher levels of temporal resolution that can allow attackers to learn finer-=
grained information. The most recent addition to this line of work is Prime+S=
cope [CCS '21], which only requires a single access to the L1 cache to confir=
m the absence of victim activity in a cache set. While significantly faster t=
han prior attacks, Prime+Scope is still an order of magnitude slower than cac=
he access. In this work, we set out to close this gap.

We draw on techniques from research into microarchitectural weird gates, soft=
ware constructs that exploit transient execution to perform arbitrary computa=
tion on cache state. We design the Spec-o-Scope gate, a new weird gate that p=
erforms 10 cache probes in quick succession, and forms the basis for our epon=
ymous attack. Our Spec-o-Scope attack achieves an order of magnitude improvem=
ent in temporal resolution compared to the previous state-of-the-art of Prime=
+Scope, reducing the measurement time from ~70 cycles to only 5 --- only one =
cycle more than an L1 cache access. We experimentally verify that our attack =
can detect timing differences in a 5 cycle resolution. Finally, using our Spe=
c-o-Scope attack, we show the first microarchitectural side-channel attack on=
 an unmodified AES S-box-based implementation, which uses generic CPU feature=
s and does not require manipulation of the operating system's scheduler.



## 2024/1575

* Title: Efficiently-Thresholdizable Batched Identity Based Encryption, with =
Applications
* Authors: Amit Agarwal, Rex Fernando, Benny Pinkas
* [Permalink](https://eprint.iacr.org/2024/1575)
* [Download](https://eprint.iacr.org/2024/1575.pdf)

### Abstract

We propose a new cryptographic primitive called "batched identity-based encry=
ption" (Batched IBE) and its thresholdized version. The new primitive allows =
encrypting messages with specific identities and batch labels, where the latt=
er can represent, for example, a block number on a blockchain. Given an arbit=
rary subset of identities for a particular batch, our primitive enables effic=
ient issuance of a single decryption key that can be used to decrypt all ciph=
ertexts having identities that are included in the subset while preserving th=
e privacy of all ciphertexts having identities that are excluded from the sub=
set. At the heart of our construction is a new technique that enables public =
aggregation (i.e. without knowledge of any secrets) of any subset of identiti=
es, into a succinct digest. This digest is used to derive, via a master secre=
t key, a single succinct decryption key for all the identities that were dige=
sted in this batch. In a threshold system, where the master key is distribute=
d as secret shares among multiple authorities, our method significantly reduc=
es the communication (and in some cases, computation) overhead for the author=
ities. It achieves this by making their costs for key issuance independent of=
 the batch size.

We present a concrete instantiation of a Batched IBE scheme based on the KZG =
polynomial commitment scheme by Kate et al. (Asiacrypt'10) and a modified for=
m of the BLS signature scheme by Boneh et al. (Asiacrypt'01). The constructio=
n is proven secure in the generic group model (GGM).

In a blockchain setting, the new construction can be used for achieving mempo=
ol privacy by encrypting transactions to a block, opening only the transactio=
ns included in a given block and hiding the transactions that are not include=
d in it.  With the thresholdized version,  multiple authorities (validators) =
can collaboratively manage the decryption process.  Other possible applicatio=
ns include scalable support via blockchain for fairness of dishonest majority=
 MPC, and conditional batched threshold decryption that can be used for imple=
menting secure Dutch auctions and privacy preserving options trading.



## 2024/1718

* Title: Drifting Towards Better Error Probabilities in Fully Homomorphic Enc=
ryption Schemes
* Authors: Olivier Bernard, Marc Joye, Nigel P. Smart, Michael Walter
* [Permalink](https://eprint.iacr.org/2024/1718)
* [Download](https://eprint.iacr.org/2024/1718.pdf)

### Abstract

There are two security notions for FHE schemes the traditional notion of IND-=
CPA, and a more stringent notion of IND-CPA$^D$.  The notions are equivalent =
if the FHE schemes are perfectly correct, however for schemes with negligible=
 failure probability the FHE parameters needed to obtain IND-CPA$^D$ security=
========== REMAINDER OF ARTICLE TRUNCATED ==========