決定的認証暗号（DAE，Deterministic Authenticated Encryption）は，データの秘匿機能と認証機能を持つ共通鍵暗号方式で，ナンスの誤用に対する安全性を持つ．研究テーマについて，メモリサイズが小さい DAE の研究が活発に行われており，ブロック暗号（BC）または Tweakable ブロック暗号（TBC）を用いることで，3s ビットのメモリで s ビット安全を達成する方式が提案されている．一方で，認証暗号の設計法として，暗号学的置換を用いる方法があり，SHA-3 や NIST の軽量暗号標準化プロセスにより，多くの研究者と標準化団体から注目されており，置換を用いた方式の設計は重要な研究テーマである．しかし，既存の置換ベース DAE は，4s ビット，またはそれ以上のメモリが必要である．そこで，本論文では，メモリサイズがより小さい置換ベースの DAE モード PALM を提案する．PALM は，BC ベースや TBC ベースの DAE と同じ，3s ビットのメモリサイズで s ビット安全を達成することを示す．PALM は，2s ビットの置換，s ビットの鍵を持つ DAE である．次に，s = 128 とし，256 ビットの置換 PHOTON256 を用いて PALM を具体化し，ハードウエア実装の性能を評価する．そして，PALM が，メモリサイズが最小の TBC ベース DAE と同等の，3,585 GE の回路となることを示す．また，置換ベースの DAE の最小のメモリサイズは 3s ビット，すなわち，PALM のメモリサイズは最小であることを示す．

Deterministic authenticated encryption (DAE) provides data integrity and authenticity with certain robustness and therefore is suited to be implemented with low memory. Previous DAE schemes for low memory are based on block ciphers (BCs) or tweakable block ciphers (TBCs), which can be implemented with 3s bits of memory for s-bit security. On the other hand, schemes based on cryptographic permutations have attracted many researchers and standardization bodies. However, existing permutation-based DAEs require at least 4s bits, or even 5s bits of memory. In this paper, we present PALM, a new permutation-based DAE mode that can be implemented only with 3s bits of memory for s-bit security, and provide a security bound and a proof of that. It implies that permutation-based DAEs achieves a competitive memory size with BC- and TBC- based DAEs. Our hardware implementation of PALM, instantiated with PHOTON256 for 128-bit security, achieves 3,585 GE, comparable with the state-of-the-art TBC-based DAE. Finally, optimality of 3s bits of memory of PALM is shown.