% !Mode:: "TeX:UTF-8"
% !TEX root=./hw1.tex
\usepackage{xeCJK}    % 写中文要用到
\usepackage{tikz}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{fullpage}
\usepackage{times}
\usepackage[hidelinks]{hyperref}
\usepackage{pdfsync}
\usepackage{microtype}
\usepackage{color}
\usepackage{cleveref}
\usepackage{enumitem}

\usepackage{lmodern}

\crefformat{footnote}{#2\footnotemark[#1]#3}
\definecolor{light-gray}{gray}{0.5}

\newcounter{questionnum}[section]

\newcommand{\paraskip}{\vskip 1em}



\renewcommand{\tablename}{表}
\renewcommand{\figurename}{图}
\renewcommand{\proof}{证明}

% \theoremstyle{plain}
% \newtheorem{theorem}{定理~}
% \newtheorem{lemma}{引理~}
% \newtheorem{axiom}{公理~}
% \newtheorem{proposition}{命题~}
% \newtheorem{prop}{性质~}
% \newtheorem{corollary}{推论~}
% \newtheorem{conclusion}{结论~}
% \newtheorem{definition}{定义~}
% \newtheorem{conjecture}{猜想~}
% \newtheorem{example}{例~}
% \newtheorem{remark}{注~}
% \newtheorem{algorithm}{算法~}


%%% BLACKBOARD SYMBOLS

% \newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\D}{\ensuremath{\mathbb{D}}}
\newcommand{\F}{\ensuremath{\mathbb{F}}}
% \newcommand{\G}{\ensuremath{\mathbb{G}}}
\newcommand{\J}{\ensuremath{\mathbb{J}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\T}{\ensuremath{\mathbb{T}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\QR}{\ensuremath{\mathbb{QR}}}

\newcommand{\Zt}{\ensuremath{\Z_t}}
\newcommand{\Zp}{\ensuremath{\Z_p}}
\newcommand{\Zq}{\ensuremath{\Z_q}}
\newcommand{\ZN}{\ensuremath{\Z_N}}
\newcommand{\Zps}{\ensuremath{\Z_p^*}}
\newcommand{\ZNs}{\ensuremath{\Z_N^*}}
\newcommand{\JN}{\ensuremath{\J_N}}
\newcommand{\QRN}{\ensuremath{\QR_{N}}}
\newcommand{\QRp}{\ensuremath{\QR_{p}}}

%%% THEOREM COMMANDS

\theoremstyle{plain}            % following are "theorem" style
\newtheorem{theorem}{定理}[section]
\newtheorem{lemma}[theorem]{引理}
\newtheorem{corollary}[theorem]{推论}
\newtheorem{proposition}[theorem]{命题}
\newtheorem{claim}[theorem]{声明}
\newtheorem{fact}[theorem]{事实}

\theoremstyle{definition}       % following are def style
\newtheorem{definition}[theorem]{定义}
\newtheorem{conjecture}[theorem]{推测}
\newtheorem{example}[theorem]{例}
\newtheorem{protocol}[theorem]{协议}

\theoremstyle{remark}           % following are remark style
\newtheorem{remark}[theorem]{注}
\newtheorem{note}[theorem]{注}
\newtheorem{exercise}[theorem]{练习}

% equation numbering style
\numberwithin{equation}{questionnum}

%%% GENERAL COMPUTING

\newcommand{\bit}{\ensuremath{\set{0,1}}}
\newcommand{\pmone}{\ensuremath{\set{-1,1}}}

% asymptotics
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\polylog}{polylog}
\DeclareMathOperator{\negl}{negl}
\newcommand{\Otil}{\ensuremath{\tilde{O}}}

% probability/distribution stuff
\DeclareMathOperator*{\E}{E}
\DeclareMathOperator*{\Var}{Var}

% sets in calligraphic type
\newcommand{\calA}{\ensuremath{\mathcal{A}}}
\newcommand{\calD}{\ensuremath{\mathcal{D}}}
\newcommand{\calF}{\ensuremath{\mathcal{F}}}
\newcommand{\calH}{\ensuremath{\mathcal{H}}}
\newcommand{\calK}{\ensuremath{\mathcal{K}}}
\newcommand{\calM}{\ensuremath{\mathcal{M}}}
\newcommand{\calX}{\ensuremath{\mathcal{X}}}
\newcommand{\calY}{\ensuremath{\mathcal{Y}}}

% types of indistinguishability
\newcommand{\compind}{\ensuremath{\stackrel{c}{\approx}}}
\newcommand{\statind}{\ensuremath{\stackrel{s}{\approx}}}
\newcommand{\perfind}{\ensuremath{\equiv}}

% font for general-purpose algorithms
\newcommand{\algo}[1]{\ensuremath{\mathsf{#1}}}
% font for general-purpose computational problems
\newcommand{\problem}[1]{\ensuremath{\mathsf{#1}}}
% font for complexity classes
\newcommand{\class}[1]{\ensuremath{\mathsf{#1}}}

% complexity classes and languages
\renewcommand{\P}{\class{P}}
\newcommand{\BPP}{\class{BPP}}
\newcommand{\NP}{\class{NP}}
\newcommand{\coNP}{\class{coNP}}
\newcommand{\AM}{\class{AM}}
\newcommand{\coAM}{\class{coAM}}
\newcommand{\IP}{\class{IP}}

%%% "LEFT-RIGHT" PAIRS OF SYMBOLS

\newcommand{\lang}[2]{#1_\texttt{#2}}

% inner product
\newcommand{\inner}[1]{\langle{#1}\rangle}
\newcommand{\innerfit}[1]{\left\langle{#1}\right\rangle}
% absolute value
\newcommand{\abs}[1]{\lvert{#1}\rvert}
\newcommand{\absfit}[1]{\left\lvert{#1}\right\rvert}
% a set
\newcommand{\set}[1]{\{{#1}\}}
\newcommand{\setfit}[1]{\left\{{#1}\right\}}
% parens
\newcommand{\parens}[1]{({#1})}
\newcommand{\parensfit}[1]{\left({#1}\right)}
% tuple = alias for parens
\newcommand{\tuple}[1]{\parens{#1}}
\newcommand{\tuplefit}[1]{\parensfit{#1}}
% square brackets
\newcommand{\bracks}[1]{[{#1}]}
\newcommand{\bracksfit}[1]{\left[{#1}\right]}
% rounding off
\newcommand{\round}[1]{\lfloor{#1}\rceil}
% floor function
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
% ceiling function
\newcommand{\ceil}[1]{\lceil{#1}\rceil}
% length of a string
\newcommand{\len}[1]{\lvert{#1}\rvert}
\newcommand{\lenfit}[1]{\left\lvert{#1}\right\rvert}
% length of some vector, element
\newcommand{\length}[1]{\lVert{#1}\rVert}
\newcommand{\lengthfit}[1]{\left\lVert{#1}\right\rVert}

%%% CRYPTO-RELATED NOTATION

% KEYS AND RELATED
\newcommand{\union}{\,\cup\,}
\newcommand{\intersection}{\,\cap\,}



\newcommand{\key}[1]{\ensuremath{#1}}

\newcommand{\pk}{\key{pk}}
\newcommand{\vk}{\key{vk}}
\newcommand{\sk}{\key{sk}}
\newcommand{\mpk}{\key{mpk}}
\newcommand{\msk}{\key{msk}}
\newcommand{\fk}{\key{fk}}
\newcommand{\id}{id}
\newcommand{\keyspace}{\ensuremath{\mathcal{K}}}
\newcommand{\msgspace}{\ensuremath{\mathcal{M}}}
\newcommand{\ctspace}{\ensuremath{\mathcal{C}}}
\newcommand{\tagspace}{\ensuremath{\mathcal{T}}}
\newcommand{\idspace}{\ensuremath{\mathcal{ID}}}

\newcommand{\concat}{\ensuremath{\|}}

% GAMES

% advantage
\newcommand{\advan}{\ensuremath{\mathbf{Adv}}}

% different attack models
\newcommand{\attack}[1]{\ensuremath{\text{#1}}}

\newcommand{\atk}{\attack{atk}} % dummy attack
\newcommand{\indcpa}{\attack{ind-cpa}}
\newcommand{\indcca}{\attack{ind-cca}}
\newcommand{\anocpa}{\attack{ano-cpa}} % anonymous
\newcommand{\anocca}{\attack{ano-cca}}
\newcommand{\euacma}{\attack{eu-acma}} % forgery: adaptive chosen-message
\newcommand{\euscma}{\attack{eu-scma}} % forgery: static chosen-message
\newcommand{\suacma}{\attack{su-acma}} % strongly unforgeable

% ADVERSARIES
\newcommand{\attacker}[1]{\ensuremath{\mathcal{#1}}}

\newcommand{\Adv}{\attacker{A}}
\newcommand{\AdvA}{\attacker{A}}
\newcommand{\AdvB}{\attacker{B}}
\newcommand{\Dist}{\attacker{D}}
\newcommand{\Sim}{\attacker{S}}
\newcommand{\Ora}{\attacker{O}}
\newcommand{\Inv}{\attacker{I}}
\newcommand{\For}{\attacker{F}}

% CRYPTO SCHEMES

\newcommand{\scheme}[1]{\ensuremath{\text{#1}}}

% pseudorandom stuff
\newcommand{\prg}{\algo{PRG}}
\newcommand{\prf}{\algo{PRF}}
\newcommand{\prp}{\algo{PRP}}

% symmetric-key cryptosystem
\newcommand{\skc}{\scheme{SKC}}
\newcommand{\skcgen}{\algo{Gen}}
\newcommand{\skcenc}{\algo{Enc}}
\newcommand{\skcdec}{\algo{Dec}}

% public-key cryptosystem
\newcommand{\pkc}{\scheme{PKC}}
\newcommand{\pkcgen}{\algo{Gen}}
\newcommand{\pkcenc}{\algo{Enc}} % can also use \kemenc and \kemdec
\newcommand{\pkcdec}{\algo{Dec}}

% digital signatures
\newcommand{\sig}{\scheme{SIG}}
\newcommand{\siggen}{\algo{Gen}}
\newcommand{\sigsign}{\algo{Sign}}
\newcommand{\sigver}{\algo{Ver}}

% message authentication code
\newcommand{\mac}{\scheme{MAC}}
\newcommand{\macgen}{\algo{Gen}}
\newcommand{\mactag}{\algo{Tag}}
\newcommand{\macver}{\algo{Ver}}

% key-encapsulation mechanism
\newcommand{\kem}{\scheme{KEM}}
\newcommand{\kemgen}{\algo{Gen}}
\newcommand{\kemenc}{\algo{Encaps}}
\newcommand{\kemdec}{\algo{Decaps}}

% identity-based encryption
\newcommand{\ibe}{\scheme{IBE}}
\newcommand{\ibesetup}{\algo{Setup}}
\newcommand{\ibeext}{\algo{Ext}}
\newcommand{\ibeenc}{\algo{Enc}}
\newcommand{\ibedec}{\algo{Dec}}

% hierarchical IBE (as key encapsulation)
\newcommand{\hibe}{\scheme{HIBE}}
\newcommand{\hibesetup}{\algo{Setup}}
\newcommand{\hibeext}{\algo{Extract}}
\newcommand{\hibeenc}{\algo{Encaps}}
\newcommand{\hibedec}{\algo{Decaps}}

% binary tree encryption (as key encapsulation)
\newcommand{\bte}{\scheme{BTE}}
\newcommand{\btesetup}{\algo{Setup}}
\newcommand{\bteext}{\algo{Extract}}
\newcommand{\bteenc}{\algo{Encaps}}
\newcommand{\btedec}{\algo{Decaps}}

% trapdoor functions
\newcommand{\tdf}{\scheme{TDF}}
\newcommand{\tdfgen}{\algo{Gen}}
\newcommand{\tdfeval}{\algo{Eval}}
\newcommand{\tdfinv}{\algo{Invert}}
\newcommand{\tdfver}{\algo{Ver}}

%%% PROTOCOLS

\newcommand{\out}{\text{out}}
\newcommand{\view}{\text{view}}

%%% COMMANDS FOR LECTURES/HOMEWORKS

\newcommand{\lecheader}{%
  \chead{\large \textbf{Lecture \lecturenum\\\lecturetopic}}

  \lhead{\small
    \textbf{\href{http://bhpan.buaa.edu.cn}{本科生课程：计算理论}\\2022年秋季}}

  \rhead{\small \textbf{主讲: 张宗洋
      }

  \setlength{\headheight}{20pt}
  \setlength{\headsep}{16pt}
}}

\newcommand{\hwheader}{%
  \chead{\Large \textbf{作业 \hwnum}}

  \lhead{\small
    \textbf{\href{https://bhpan.buaa.edu.cn/link/AR80F94437CCF24C84A7B09DA4CAFAB8AA}{计算理论}\\2023年秋季}}

  \rhead{\small \textbf{主讲: 张宗洋
      \\姓名: \studentname}}

  \setlength{\headheight}{20pt}
  \setlength{\headsep}{16pt}
  
  \headrule
}

\newcommand{\examheader}{%
  \chead{\Large \textbf{测试 \\ \duedate}}
  
\lhead{\small
    \textbf{\href{http://bhpan.buaa.edu.cn}{计算理论导引}\\2022年春季}}

  \rhead{\small \textbf{主讲: 张宗洋
      \\姓名: \studentname}}

  \setlength{\headheight}{20pt}
  \setlength{\headsep}{16pt}
  
  \headrule
}
  
	
\newcommand{\hint}[1]{\href{http://www.cims.nyu.edu/~regev/cgi-bin/hints/index.html?#1}{{\textcolor{light-gray}{I need a hint! (ID #1)}}}}

\newcommand{\hinttext}[2]{\href{http://www.cims.nyu.edu/~regev/cgi-bin/hints/index.html?#1}{{\textcolor{light-gray}{#2 (ID #1)}}}}

\newcommand{\hintcost}[2]{\href{http://www.cims.nyu.edu/~regev/cgi-bin/hints/index.html?#1}{{\textcolor{light-gray}{I need a hint for #2 points! (ID #1)}}}}
	
\newcommand{\moreinfo}[1]{\href{http://www.cims.nyu.edu/~regev/cgi-bin/hints/index.html?#1}{{\textcolor{light-gray}{I'm done solving and want to know more! (ID #1)}}}}